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