Shortest s-t path: Given graph and is the length of the direct edge between and , we wish to compute a shortest path from to . We assume that for every .
Consider the following algorithm (Dijkstra) for shortest paths.
- Assign tentative distances to every vertex as , if and otherwise .
- Let be the vertex with smallest .
- For every neighbor of , if then update .
- Add to and iterate till .
Lemma: Every time we add a vertex with the smallest then where is the actual shortest path length from to .
Proof: Consider a shortest to path and assume for the sake of contradiction that . Since , it must leave at some vertex . Let be the vertex immediately before in (hence ). By induction and when we included in we must have relaxed so that . Since , we arrive at a contradiction.
Running Time: The iteration runs for times (since it stops only when ). Inside the loop we only look at an edge once – once we update a vertex using that edge we never use it to update that same vertex again. To find the vertex with the shortest we can use a min-heap and then the run time is .
Variant of the problem
Suppose we want to find a shortest path between and that uses at most edges. Let be defined as the shortest path from to using at most edges. We claim that . This is because the optimal path from to using at most edges could either use atmost edges or it must have used at most edges to go from to for some and then used the edge .
How do we turn this into an algorithm? Consider a table whose rows are indexed by pairs of vertices and the columns are indexed by . The entry corresponds to the shortest to path using at most edges. Note that we can fill the first column trivially: . Suppose we have inductively filled up the first columns. To fill the column we simply use the formula . Note that since column was already filled, all the values are available to us. The run time of this algorithm is .
All Pairs Shortest Path
Let be the shortest path from to using vertices . Then we can write . One can convert this into a table filling algorithm with running time .