(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?