(LONGEST-PATH) S-T LONGEST PATH IN ACYCLIC DIGRAPH
Instance: Acyclic DiGraph 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 LONGEST-PATH) |
+------------------------------------------------------------+
| If P is LONGEST-PATH w.r.t the length function L1 |
| and P is LONGEST-PATH w.r.t the length function L2 |
| then P is LONGEST-PATH w.r.t the length function L1+L 2 |
+------------------------------------------------------------+
Let epsilon = min {L(e): e adjacent to s}
define L1(e) = epsilon for all e adjacent to s and 0 otherwise.
Q1: All 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 LONGEST-PATH w.r.t. L2.
P (and any simple path) is LONGEST-PATH w.r.t. L1 (see Q1).
By the "Local-Ratio Theorem" P is LONGEST-PATH w.r.t. L=L1+L2.
Q: What to do with zero weight edges?