May 27, 2009 Leave a comment
A path, as the name suggests connects 2 vertices in a graph. A shortest path is a path of minimum length.
If we have a particular vertex, say s, and need to find shortest paths from s to all other vertices of the graph. It is called the Single Source Shortest Path Problem (SSSP).
We may also want to find shortest paths between every possible pair of vertices in the graph. This is the All Pairs Shortest Paths Problem (APSP).
How do we find a shortest path between 2 vertices, say s and v?
Simple. Proceed in a manner that would remind us of Prim’s algorithm, which was discussed in the previous post.
We find the shortest path by sort of growing a cloud. Initially, we got only s. Now, choose that vertex which is closest to s. So now the cloud has 2 vertices, and the “diameter” of the cloud is the distance of this newly-added vertex, say x, from s.
Next step. Now, find a vertex that is father from s than x, but is closer to s than any of the other vertices (or at least no farther than any of them). Call this vertex, y. Now, the path from s to y, will either be direct (i.e. one edge) or would be the addition of edge (x,y) to the path from s to x.
We continue in the same manner. Lets see one more step.
Suppose that the most recent vertex added to the cloud is d, and that the shortest path from s to d is s-> a -> b -> c -> d. How do we choose the next vertex to be added to the cloud?
Select the vertex that is farther from s than d (or at least no closer) and is closer to s than any other vertex outside the cloud (or at least no farther). This vertex, say e, will have a shortest path from s, that is either a direct path (s->e), or an indirect one (s -> a -> e, or s-> a ->b ->e, or s-> a -> b ->c ->e, or s-> a -> b -> c-> d-> e).
Keep on adding vertices to the cloud until vertex v, also enters the cloud.
For the SSSP problem, keep adding vertices until the all vertices have been added.
This is known as Dijkstra’s algorithm.
It’s quite simple and also very well-known. Incidentally, it was discovered 50 years ago (1959). 🙂