1、最短路徑最短路徑帶權圖帶權圖G=, 其中其中w:ER. e E, w(e)稱作稱作e的的權權. e=(vi,vj), 記記w(e)=wij . 若若vi,vj不不相鄰相鄰, 記記wij = . 設設L是是G中的一條路徑中的一條路徑, L的所有邊的權之和稱作的所有邊的權之和稱作L的的權權, 記作記作w(L).u和和v之間的之間的最短路徑最短路徑: u和和v之間權最小的通路之間權最小的通路.例例1 L1=v0v1v3v5, w(L1)=10, L2=v0v1v4v5, w(L2)=12, L3=v0v2v4v5, w(L3)=11.1標號法標號法(E.W.Dijkstra, 1959) )(ril

2、設帶權圖設帶權圖G=, 其中其中 e E, w(e) 0.設設V=v1,v2,vn, 求求v1到其余各頂點的最短路徑到其余各頂點的最短路徑p標號標號(永久性標號永久性標號) : 第第r步獲得的步獲得的v1到到vi最短路徑的最短路徑的權權t標號標號(臨時性標號臨時性標號) : 第第r步獲得的步獲得的v1經過經過p標號頂點標號頂點到達到達vi的路徑的最小權的路徑的最小權, 是是v1到到vi的最短路徑的權的上的最短路徑的權的上界界第第r步通過集步通過集Pr=v | v在第在第r步已獲得永久性標號步已獲得永久性標號第第r步未通過集步未通過集Tr=V-Pr)(ril2標號法標號法(續續) )0(il1.

3、 v1獲獲p標號標號: =0, P0=v1, T0=V-v1, vj(j=2,3,n)獲獲t 標標 號號: =wij. 令令r1.2. 設設 , vi獲得獲得p標號標號: . 令令 Pr=Pr-1 vi, Tr=Tr-1-vi. 若若Tr=, 則結束則結束.3. vj Tr, 令令 令令r=r+1, 轉轉2.)1()( ririll)0(jlmin)1()1(1 rjTvrillrj,min)()1()(ijrirjrjwlll 算法算法: :3標號法求最短路徑第一步：4 標號法求標號法求v0到到v5的最短路徑的最短路徑 v0 v1 v2 v3 v4 v5 0 0 1 4 vir因為第一步因為

4、第一步v0只能夠到達只能夠到達v1和和v2，所以，所以v1和和v2下面寫到達下面寫到達的權重，而的權重，而v3v5寫無窮大。寫無窮大。標號法求最短路徑第二步：5 標號法求標號法求v0到到v5的最短路徑的最短路徑 v0 v1 v2 v3 v4 v5 0 0 1 4 1 1/v0 3 8 6 vir因為第一步得到的數字當中除了已經確定的因為第一步得到的數字當中除了已經確定的0以外，以外，1最小，最小，所以到達所以到達v1的最短路徑確定了，為的最短路徑確定了，為1，并且通過，并且通過v0。因為通過因為通過v1到達到達v2需要需要3步，比步，比4小，所以小，所以v2處寫處寫3。同理，因為通過同理，因為

5、通過v1到達到達v3和和v4的權重和小于正無窮。的權重和小于正無窮。標號法求最短路徑第三步：6 標號法求標號法求v0到到v5的最短路徑的最短路徑 v0 v1 v2 v3 v4 v5 0 0 1 4 1 1/v0 3 8 6 2 3/v0 8 4 vir因為第二步得到的數字當中因為第二步得到的數字當中3最小，最小，v2最短為最短為3。因為通過因為通過v2不能直接到達不能直接到達v3，所以，所以v3下面還是下面還是8。通過通過v2到達到達v4需要需要4到達不了到達不了v5標號法求最短路徑第四步：7 標號法求標號法求v0到到v5的最短路徑的最短路徑 v0 v1 v2 v3 v4 v5 0 0 1 4

6、 1 1/v0 3 8 6 2 3/v0 8 4 3 7 4/v2 10vir標號法求最短路徑第五步：8 標號法求標號法求v0到到v5的最短路徑的最短路徑 v0 v1 v2 v3 v4 v5 0 0 1 4 1 1/v0 3 8 6 2 3/v0 8 4 3 7 4/v2 10 4 7/v4 9vir v0 v1 v2 v3 v4 v5 0 0 1 4 1 1/v0 4 8 6 2 4/v0 8 5 3 8 5/v2 6 4 8 6/v4 5 8/v1 w 0 1 4 8 5 6 =v0v1v2v4v3v5, w( )=6vir9同理得到第五行，只是得到第五行以后所有都標紅了，也就是所有都結束同理得到第五行，只是得到第五行以后所有都標紅了，也就是所有都結束了，最后加一行，把所有標紅的數字重新寫一遍，這些數字就是到達相應了，最后加一行，把所有標紅的數字重新寫一遍，這些數字就是到達相應vi所需要的最短路徑所需要的最短路徑求求v0到到v5的最短路徑的最短路徑 v0 v1 v2 v3 v4 v5 0