Program ComicsBehavior Comic
Welcome! We're going to apply Dijkstra's to find the shortest path from the start vertex to the end vertex of a graph with non-negative weights. The graph below is a directed graph, meaning its edges have direction. You can also think of this as finding the shortest driving directions on a map, where each edge is a one-way street and each edge weight is the distance (or time) to travel that street.
Explore the start. The minimum distance from the start to start is 0.
Next, relax all the edges going out of vertex v. That is, for each neighboring vertex, update its best distance so far value. If the distance of the new path along the edge is less than the best distance so far, then update the best distance so far. Also update the previous vertex of this neighbor to be vertex v, in order to track the shortest paths.
Explore vertex 2 because it has the smallest best distance so far among the unexplored vertices. Vertex 2’s distance value of 1 is less than vertex 1’s distance value of 2 and all the other vertices’ distance values of infinity.
Again, relax all the edges going out of the vertex, just one edge in this case.
Explore vertex 1 because it has the smallest best distance so far among the unexplored vertices. And relax the edges.
And repeat. Notice how the goal vertex was reached but we continue searching until the goal vertex is actually explored.
Explore vertex 5. When a vertex is reached in an explore step (like this one), its shortest path and minimum distance from the start has been found. That statement deserves a proof but for now let's keep going.
Just a lonely and agitated 5. No shared edges to relax.
The goal is now explored so the shortest path has been found with a distance value of 10! But the vertices in the path still must be identified.
Using the previous vertices tracked in the relax step, repeatedly follow edges backward until the start is reached.
