競賽及點評圖論與網(wǎng)絡(luò)最優(yōu)化lecture

1、Dijkstras Algorithm 單源最短路問題Problem Solved by DijkstrasSingle-source shortest-paths problem Edge weight =0Input: A graph G=(V, E) and a source s, and a nonnegative function w: ER+Output: For each vertex v, shortest path weight d(s,v), and a shortest path if exists.The Dijkstra AlgorithmDIJKSTRA(G,w,s

2、)Initialize-Single-Source(G,s)S QVG while Qdo uEXTRACT-MIN(Q)SSu for each v Adju do RElAX(u,v,w)Dijkstras Algorithm - exampleInitial GraphDistance to all nodes marked SourceMark 0 Dijkstras Algorithm - OperationInitial GraphSourceRelax edges leaving sourceS= S=sDijkstras Algorithm - OperationRed arr

3、ows show predecessorsSort vertices and choose closestRelax u and a shorter path via xexistsRelax yDijkstras Algorithm - OperationS is now s, x Sort vertices and choose closestRelax v and a shorter path via yexistsDijkstras Algorithm - OperationS is now s, x, y Sort vertices and choose closest, uUpda

4、te dvDijkstras Algorithm - OperationS is now s, x, y, u Finally add vDijkstras Algorithm - OperationS is now s, x, y, u Pre-decessors show shortest paths sub-graph Correctness of DijkstrasTheorem 24.6Dijkstras algorithm, run on a weighted,directed graph G=(V, E), with non-negative weight function w

5、and source s, terminates with du= d(s,u) for all vertices uV.Proof (by contradiction)Since S=V in the end, we only need to prove that for each vertex v added to S, there holds dv= d(s, v) when v is added to S.Suppose that u is the first vertex for which du d(s, u) when it was added to S Noteu is not

6、 s because ds = 0= d(s, s)There must be a path s.u, since otherwise du= d(s, u) = .Since theres a path, there must be a shortest path (note there is no negative cycle). Dijkstras Algorithm - ProofLet sxyu be a shortest pathfrom s to u, where at the moment u is chosen to S, x is in S and y is the fir

7、st outside S When x was added to S, dx = d(s, x)Edge xy was relaxed at that time, so at time u is chosen, dy = d(s, y)Applications-1最大可靠路給定一個通訊網(wǎng)絡(luò)N ,設(shè)弧aij 的完好概率為pij . 設(shè)路P 由若干條弧組成, 則定義路P的完好概率為:從頂點v0 到頂點vi 之間完好概率最大的路, 稱為從v0 到vi的最大可靠路.方法：定義每條弧的權(quán)重為wij=-log pij。則每條路的長度與其完好概率的關(guān)系為：w(P)=-logp(P).Applications

8、-2最大容量路給定一個運輸網(wǎng)絡(luò)N , 對N 的每條弧aij , 都有一個表示通過能力的參數(shù)cij 0,cij 一般稱為容量. 它的實際意義可以是道路所能通過車輛的最大高度, 或者是所能通過車輛的最大重量, 或者是單位時間內(nèi)所能通過的最大車流量等等. N 的每一條路P 的容量定義為P 的所有弧的最小容量, 即求v0 到其它各點最大容量路的算法可以通過對Dijkstra 算法進行修改得到, 只要將算法中弧權(quán)改為弧容量, 加法運算改為求最小的運算, 并將原來求最小的運算改為求最大的運算就可以得到求最大容量的算法.Applications-3最大期望容量路給定一個通訊網(wǎng)絡(luò)N = (V;A), N 的每條弧(可視為一