DIJKSTRA(G.w.s) 1 INITIALIZE-SINGLE-SOURCE(G.S) Proof We use the following loop invariant: 2S=0 3 0=G.V At the start of each iteration of the while loop of lines 4-8,v.d=(s,v) 4 while O≠g for each vertex v∈S. 5 EXTRACT-MIN(O) 6 S=SUfu 7 for each vertex v G.Adjlu] 8 RELAX(u.V.w) 问题11： 3 Diistra算法对每条边最多relax 一次，而且不要求输入是DAG 它付出的代价是什么？为什么必 须如此？ 3 3 3 3 0 02 1 3 13 - 3 1 4 2 1 3 3 - 3 1 4 0 3 0 1 2 1 3 13 1 4 0 3 0 2