(SHORTEST-PATH) S-T SHORTEST PATH
Instance: [Di]Graph G=(V,E), a pair of vertices s,t in V.
For each e in E a length L(e)>=0;
Solution: A path P from s to t;
Measure : The total path length, L(P) (i.e. Sum {L(e): e in P})
+------------------------------------------------------------+
| The "Local-Ratio Theorem" (oriented for SHORTEST-PATH) |
+------------------------------------------------------------+
| If P is SHORTEST-PATH w.r.t the length function L1 |
| and P is SHORTEST-PATH w.r.t the length function L2 |
| then P is SHORTEST-PATH w.r.t the length function L1+L2 |
+------------------------------------------------------------+
Let epsilon = min {L(e): e adjacent to s}
define L1(e) = epsilon for all e adjacent to s and 0 otherwise.
Q1: All simple paths from s to t have same L1's length. Why?
The algorithm: iteratively subtract L1 as above.
Induction hyp. implies that recusive call with L2=L-L1
would return a path P which is SHORTEST-PATH w.r.t. L2.
P (and any simple path) is SHORTEST-PATH w.r.t. L1 (see Q1).
By the "Local-Ratio Theorem" P is SHORTEST-PATH w.r.t. L=L1+L2.
Q2: What to do with zero weight edges?
Q3: The above algorithm is equivalent to Dijkstra's. Why?