Dijkstra's Shortest Path Algorithm
The single-source shortest path problem on a graph is solved every time a user requests a route on a route planning application such as Google Maps or in the navigation software built into cars. The problem is defined as follows:
"Given a directed graph, G - < V, E > where V is the set of vertices and E is the set of edges, each of which is associated with an edge weight, a source vertex, and a destination vertex, find a minimum-cost path from a source to a destination."
Dijkstra's algorithm works for graphs with non-negative edge weights and is only a slight modification of Prim's MST algorithm, with two major changes:
- Instead of setting labels on every vertex equal to the minimum distance from the frontier, Dijkstra's algorithm sets the labels on each vertex with the distance equal to the total distance of the vertex from the source.
- Dijkstra's algorithm terminates if the destination vertex is popped from...
