Dijkstra's Shortest Path Algorithm

[qingquan-li]

Definition: The shortest path algorithm, is a greedy algorithm, developed by Dijkstra. Dijkstra's algorithm is a method for finding the shortest path from a single source vertex to all other vertices in a graph.

Type of Graph: Works on both directed and undirected graphs, as long as the weights are non-negative.

Mechanism:

• Initially, set the distance to the source vertex as 0 and all other vertices as infinity (∞).
• Use a priority queue to keep track of vertices with the shortest distance that haven't been processed (visited) yet.
• Repeatedly extract the vertex with the smallest distance, update the distances to its adjacent vertices, and mark it as processed (visited).

Greedy Approach: At every step, the algorithm greedily chooses the next vertex with the smallest known distance from the source.