Graph DataStructure

Graph always seems to be the complex data structure. Here is the one stop list of all the algorithm and summary of each.

1. Dijkstra Algorithm: Shortest Path Problem from given starting node : Minimum spanning tree with given starting node: Greedy Method
2. Bellman-Ford Algo: Shortest Path Problem from given starting node : Minimum spanning tree with given starting node with any Negative Weights
3. Prim’s Algo
4. Kruskal’s Algo
5. Dijkstra Algo
6. Floyd Warshall Algo

1.) Dijkstra Algorithm :
Dijkstra Algo is the basic and the simplest algorithm for finding the shortest path from the given starting point in a given connect cyclic/acyclic graph.
Points:

1.) Algo gives the shortest path from GIVEN starting point to other (Minimum spanning tree with given starting node)
2.) Works for cyclic/acyclic graph
3.) Negative weights cannot cater through this Algo (*negative weights signifies business logic )
Below are the Leetcode questions related to Dijkstra Algo:

1. https://leetcode.com/problems/path-with-maximum-probability/
2. https://leetcode.com/problems/network-delay-time/ ()
3. https://leetcode.com/problems/the-maze-ii/
4. https://leetcode.com/problems/the-maze-iii/
5. https://leetcode.com/problems/path-with-minimum-effort/
6. https://leetcode.com/problems/find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance/

Share on Facebook

Tweet

Follow us