[FEATURE REQUEST] Want to add few popular Greedy algorithms
Vanraj8169 opened this issue · 4 comments
What would you like to Propose?
I want to add following algorithms in Greedy.
- Job Sequencing Problem
- Dijkstra Shortest Path Algorithm
- Graph Coloring Algorithm
- Boruvka's Algorithm
- Prim's Minimum Spanning Tree Algorithm
Job Sequencing Problem
Problem Statement :
Given an array of jobs where every job has a deadline and associated profit if the job is finished before the deadline. It is also given that every job takes a single unit of time, so the minimum possible deadline for any job is 1. Maximize the total profit if only one job can be scheduled at a time.
Examples:
Input: Four Jobs with following deadlines and profits
JobID Deadline Profit
a 4 20
b 1 10
c 1 40
d 1 30
Output: Following is maximum profit sequence of jobs: c, a
Dijkstra Shortest Path Algorithm
Given a graph and a source vertex in the graph, find the shortest paths from the source to all vertices in the given graph.
Examples:
Input: src = 0, the graph is shown below.
Output: 0 4 12 19 21 11 9 8 14
Explanation: The distance from 0 to 1 = 4.
The minimum distance from 0 to 2 = 12. 0->1->2
The minimum distance from 0 to 3 = 19. 0->1->2->3
The minimum distance from 0 to 4 = 21. 0->7->6->5->4
The minimum distance from 0 to 5 = 11. 0->7->6->5
The minimum distance from 0 to 6 = 9. 0->7->6
The minimum distance from 0 to 7 = 8. 0->7
The minimum distance from 0 to 8 = 14. 0->1->2->8
Graph Coloring Algorithm
Problem Statement:
Graph coloring problem involves assigning colors to certain elements of a graph subject to certain restrictions and constraints. In other words, the process of assigning colors to the vertices such that no two adjacent vertexes have the same color is caller Graph Coloring.
Boruvka's Algorithm
Problem Statement
Borvka's algorithm approach is a greedy algorithm for locating the Minimum Spanning tree in a graph or the Minimum spanning forest in the case of an unconnected network.
Its most well-known use is for determining the minimal spanning tree in a graph.
Prim's Minimum Spanning Tree Algorithm
Problem Statement
Prim’s algorithm is used to find the Minimum Spanning Tree for a given graph. But, what is a Minimum Spanning Tree, or MST for short? A minimum spanning tree T(V’, E’) is a subset of graph G(V, E) with the same number of vertices as of graph G (V’ = V) and edges equal to the number of vertices of graph G minus one (E’ = |V| - 1). Prim's approach identifies the subset of edges that includes every vertex in the graph, and allows the sum of the edge weights to be minimized.
Prim’s algorithm starts with a single node and works its way through several adjacent nodes, exploring all of the connected edges along the way. Edges with the minimum weights that do not cause cycles in the graph get selected for t inclusion in the MST structure. Hence, we can say that Prim’s algorithm takes a locally optimum decision in order to find the globally optimal solution. That is why it is also known as a Greedy Algorithm.
Issue details
I want to contribute this algorithms in Greedy.
I will use Java/C++ to write code for every algorithm.
Please assign me this issue.
Additional Information
No response
Hello! @Vanraj8169, I would like to contribute to this repository by providing the solutions for your list of problems. So could you please let me know if you have started working on this or can I get this issue assigned to myself ?
Issue has not yet been assigned to me
This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.
Please reopen this issue once you add more information and updates here. If this is not the case and you need some help, feel free to seek help from our Gitter or ping one of the reviewers. Thank you for your contributions!