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

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

3、 v1獲獲p標(biāo)號標(biāo)號: =0, P0=v1, T0=V-v1, vj(j=2,3,n)獲獲t 標(biāo)標(biāo) 號號: =wij. 令令r1.2. 設(shè)設(shè) , vi獲得獲得p標(biāo)號標(biāo)號: . 令令 Pr=Pr-1 vi, Tr=Tr-1-vi. 若若Tr=, 則結(jié)束則結(jié)束.3. vj Tr, 令令 令令r=r+1, 轉(zhuǎn)轉(zhuǎn)2.)1()( ririll)0(jlmin)1()1(1 rjTvrillrj,min)()1()(ijrirjrjwlll 算法算法: :3標(biāo)號法求最短路徑第一步：4 標(biāo)號法求標(biāo)號法求v0到到v5的最短路徑的最短路徑 v0 v1 v2 v3 v4 v5 0 0 1 4 vir因?yàn)榈谝徊揭驗(yàn)?/p>

4、第一步v0只能夠到達(dá)只能夠到達(dá)v1和和v2，所以，所以v1和和v2下面寫到達(dá)下面寫到達(dá)的權(quán)重，而的權(quán)重，而v3v5寫無窮大。寫無窮大。標(biāo)號法求最短路徑第二步：5 標(biāo)號法求標(biāo)號法求v0到到v5的最短路徑的最短路徑 v0 v1 v2 v3 v4 v5 0 0 1 4 1 1/v0 3 8 6 vir因?yàn)榈谝徊降玫降臄?shù)字當(dāng)中除了已經(jīng)確定的因?yàn)榈谝徊降玫降臄?shù)字當(dāng)中除了已經(jīng)確定的0以外，以外，1最小，最小，所以到達(dá)所以到達(dá)v1的最短路徑確定了，為的最短路徑確定了，為1，并且通過，并且通過v0。因?yàn)橥ㄟ^因?yàn)橥ㄟ^v1到達(dá)到達(dá)v2需要需要3步，比步，比4小，所以小，所以v2處寫處寫3。同理，因?yàn)橥ㄟ^同理，因?yàn)?/p>

5、通過v1到達(dá)到達(dá)v3和和v4的權(quán)重和小于正無窮。的權(quán)重和小于正無窮。標(biāo)號法求最短路徑第三步：6 標(biāo)號法求標(biāo)號法求v0到到v5的最短路徑的最短路徑 v0 v1 v2 v3 v4 v5 0 0 1 4 1 1/v0 3 8 6 2 3/v0 8 4 vir因?yàn)榈诙降玫降臄?shù)字當(dāng)中因?yàn)榈诙降玫降臄?shù)字當(dāng)中3最小，最小，v2最短為最短為3。因?yàn)橥ㄟ^因?yàn)橥ㄟ^v2不能直接到達(dá)不能直接到達(dá)v3，所以，所以v3下面還是下面還是8。通過通過v2到達(dá)到達(dá)v4需要需要4到達(dá)不了到達(dá)不了v5標(biāo)號法求最短路徑第四步：7 標(biāo)號法求標(biāo)號法求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標(biāo)號法求最短路徑第五步：8 標(biāo)號法求標(biāo)號法求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同理得到第五行，只是得到第五行以后所有都標(biāo)紅了，也就是所有都結(jié)束同理得到第五行，只是得到第五行以后所有都標(biāo)紅了，也就是所有都結(jié)束了，最后加一行，把所有標(biāo)紅的數(shù)字重新寫一遍，這些數(shù)字就是到達(dá)相應(yīng)了，最后加一行，把所有標(biāo)紅的數(shù)字重新寫一遍，這些數(shù)字就是到達(dá)相應(yīng)vi所需要的最短路徑所需要的最短路徑求求v0到到v5的最短路徑的最短路徑 v0 v1 v2 v3 v4 v5 0