1. Generalize principles from experience: algorithms
To tell a computer what to do, we need to first come up with an algorithmic procedure.
Greedy strategies are a natural way to proceed. That is, starting from the source vertex A, and going all the way along the known shortest path. Keep exploring new vertices until we reach destination E. And indeed, this approach satisfies our example.
The intuition is that, along the shortest path to a destination, every intermediate node is visited in the shortest path as well. (Of course this intuition assumes that all edges have positive weights. This may not hold true, depending on the applications. We will discuss this in detail later).
So here is the algorithmic procedure:
- Some setup: (1) bookkeep the vertices we have visited: a set (visited), (2) remember the known shortest distances to each vertex that use only discovered vertices: another set distance(u). Every vertex’s distance is initially infinity, except for the source vertex is 0.
- Now we start exploring: first we visit the vertex that has the known shortest path so far, say it’s u. (Initially it would be the source vertex).
- When standing at vertex u, we look around the out-going edges. Each edge, say(u,v), gives us a path to vertex v that uses vertex u as the last but only one step. If any of them is indeed a shorter path to v , or the first path we found to v, hooray we can update our set of shortest paths now. Otherwise ignore and keep going.
- We are done with vertex u, so we add it into our visited set.
- Go back to step 2, keep exploring until we have visited all vertices.
distance can now tell us the global shortest distances, because it’s used to keep the shortest distances using only visited nodes. And all vertices are visited when the algorithm finishes.
We just reinvented Dijkstra’s algorithm. Of course, there are many other algorithms for finding the shortest path. But the point is, we need a algorithmic procedure to solve the problem.