6.5最短有向路问题

第五节最短有向路问题最短有向路方程求最短有向路的Dijkstra算法算法步骤算法复杂性最短有向路方程问题：寻求有向网络中中自某一指定点i到另一指定点j间的最短有向路.给定有向网络G=(N,A,W),设P为G中的一条有向路,P的权(或路长):W(P)=∑W(a)a∈P定理6.5.1设有向网络G中不含非正有向回路，并且从点1到其余点都有有限长度的有向路，那么下式有唯一有限解。u1=0uj=min{uk+ukj},j=2,3,…,n其中，uj和uk分别表示自点1到点j和点k的最短有向路的长度，wkj表示弧(k,j)的长度。k≠j{定理6.5.2设uj是有向网络G中自点1到点j的最短有向路的长度，并且对所有的j=2,3,…,n,uj为有限值,若网络G中的点能编成如下的序号2,3,…,n,使得若ij，有ui≤uj且wji≥0，但等号不同时成立或者uiuj,且wji=+∞,即(j,i)∉A。则方程(6.5.2)可简化为u1=0uj=min{uk+wkj},j=2,3,…,nkj{最短有向路方程续定理6.5.3设G=(N,A,W)是一个弧权为正值的有向网络,则在G中,任意一条最短有向路的长都大于它的真子有向路的长.最短有向路方程续G中自点1到其他各点最短有向路的长可按大小排列如下:0=u1≤u2≤…≤unDijkstra算法的步骤第3步(修改临时标号)对T中每一点j,置uj=min{uj,uk+wkj},然后返回第1步例用Dijkstra算法求解下图所示有向网络中自点1到其他各点的最短有向路。其中每条弧上的数表示其权值。16534251225343647第1步(开始)置u1=0,uj=w1j,j=2,3,…,n,P={1},T={2,3,…,n}.第2步(指出永久编号)在T中寻找一点k，使得.uk=min{uj},置P=P∪{k},T=T-{k}.若T=φ,终止；否则，进行第3步。j∈TDijkstra算法的复杂性这个算法经过n-1次循环必结束.在第2步中要做(n-2)(n-1)/2次比较.在第3步中要做(n-2)(n-1)/2次加法和(n-2)(n-1)/2次比较.所以，总的计算量约为O(n2).