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