最短路問題-D算法

1、最 短 路 問 題,一、問題的提法及應(yīng)用背景,（1）問題的提法尋求網(wǎng)絡(luò)中兩點(diǎn)間的最短路就是尋求連接這兩個(gè)點(diǎn)的邊的總權(quán)數(shù)最小的通路。（注意：在有向圖中，通路開的初等鏈中所有的弧應(yīng)是首尾相連的。） （2）應(yīng)用背景管道鋪設(shè)、線路安排、廠區(qū)布局、設(shè)備更新等。,二、最短路算法,1 D氏標(biāo)號(hào)法（Dijkstra）；邊權(quán)非負(fù) 2. 列表法（福德法）；有負(fù)權(quán)，無負(fù)回路,1D氏標(biāo)號(hào)法（Dijkstra） （1）求解思路從始點(diǎn)出發(fā)，逐步順序地向外探尋，每向外延伸一步都要求是最短的。,（2）使用條件網(wǎng)絡(luò)中所有的弧權(quán)均 非負(fù)，即 。,（3）選用符號(hào)的意義： P 標(biāo)號(hào)（Permanent固定/永久性標(biāo)號(hào)） 從始點(diǎn)到該標(biāo)

2、號(hào)點(diǎn)的最短路權(quán) T 標(biāo)號(hào)（Temporary臨時(shí)性標(biāo)號(hào)） 從始點(diǎn)到該標(biāo)號(hào)點(diǎn)的最短路權(quán)上界,（4）計(jì)算步驟及例子：,第一步：給起始點(diǎn)v1標(biāo)上固定標(biāo)號(hào) , 其余各點(diǎn)標(biāo)臨時(shí)性標(biāo)號(hào) T(vj)=, j1;,= l1j,若網(wǎng)絡(luò)圖中已無滿足此條件的T標(biāo)號(hào)點(diǎn)，停止計(jì)算。,第三步： 令 , 然后將 的T 標(biāo)號(hào)改成P 標(biāo)號(hào)，轉(zhuǎn)入第二步。此時(shí)，要注意將第二步中的 改為 。,例一、 用Dijkstra算法求下圖從v1到v6的最短路。,解 （1）首先給v1以P標(biāo)號(hào)，給其余所有點(diǎn)T標(biāo)號(hào)。,（2）,例一、 用Dijkstra算法求下圖從v1到v6的最短路。,（4）,（5）,（6）,反向追蹤得v1到v6的最短路為：,2,3

3、,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,求從1到8的最短路徑,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,min d12,d14,d16=min 0+2,0+1,0+3=min 2,1,3=1 X=1,4, p4=1,p4=1,p1=0,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,4,min d12,d16,d42,d47=min 0+2,0+3,1+10,1+2=min 2,3,11,3=2 X=1,2,4, p2=2,p1=0,

4、p4=1,p2=2,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,2,4,min d16,d23,d25,d47=min 0+3,2+6,2+5,1+2=min 3,8,7,3=3 X=1,2,4,6, p6=3,p2=2,p4=1,p1=0,p6=3,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,2,4,6,min d23,d25,c47,d67=min 2+6,2+5,1+2,3+4=min 8,7,3,7=3 X=1,2,4,6,7, p7=3,p2=2,p4=1,p1=0,p

5、6=3,p7=3,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,2,4,6,7,min d23,d25,d75,d78=min 2+6,2+5,3+3,3+8=min 8,7,6,11=6 X=1,2,4,5,6,7, p5=6,p2=2,p4=1,p1=0,p6=3,p7=3,p5=6,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,2,4,6,7,min d23,d53,d58,d78=min 2+6,6+9,6+4,3+8=min 8,15,10,11=8 X=1,2,3,4,5,6,7, p3=8,p2=2,p4=1,p1=0,p6=3,p7=3,p5=6,p3=8,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,2,3,4,6,7,min d38,d58,d78=min 8+6,6+4,3+7=min 14,10,11=10 X=1,2,3,4,5,6,7,8, p8=10,p2=2,p4=1,p1=0,p6=3,p7=3,p5=6,p3=8,p8=10,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3