最短路問題迪杰斯特拉算法課件

最短路問題

*

最短路問題

*1一、問題的提法及應用背景

（1）問題的提法——尋求網(wǎng)絡中兩點間的最短路就是尋求連接這兩個點的邊的總權(quán)數(shù)最小的通路。（注意：在有向圖中，通路——開的初等鏈中所有的弧應是首尾相連的。）

（2）應用背景——管道鋪設(shè)、線路安排、廠區(qū)布局、設(shè)備更新等。*一、問題的提法及應用背景（1）問題的提法——尋求網(wǎng)絡中兩點2二、最短路算法

1．

D氏標號法（Dijkstra）；邊權(quán)非負2.列表法（福德法）；有負權(quán)，無負回路4v1v2v3v4v6v5v722561413412*二、最短路算法

1．D氏標號法（Dijkstra）；邊權(quán)非31．D氏標號法（Dijkstra）（1）求解思路——從始點出發(fā)，逐步順序地向外探尋，每向外延伸一步都要求是最短的。

（2）使用條件——網(wǎng)絡中所有的弧權(quán)均

非負，即。*1．D氏標號法（Dijkstra）（2）使用條件——網(wǎng)絡中所4（3）選用符號的意義：

①

P

標號（Permanent固定/永久性標號）——從始點到該標號點的最短路權(quán)②

T

標號（Temporary臨時性標號）——從始點到該標號點的最短路權(quán)上界*（3）選用符號的意義：*5（4）

計算步驟及例子：第一步：給起始點v1標上固定標號,其余各點標臨時性標號T(vj)=,j1;=l1j第二步：考慮滿足如下條件的所有點①與v1相鄰的點，即;②具有T標號，即，

為T

標號點集.

修改的T標號為，并將結(jié)果仍記為T(vj)。svj?若網(wǎng)絡圖中已無滿足此條件的T標號點，停止計算。*（4）

計算步驟及例子：第一步：給起始點v1標上固定標號6第三步：令,然后將的T標號改成P

標號，轉(zhuǎn)入第二步。此時，要注意將第二步中的改為。*第三步：令7例一、用Dijkstra算法求下圖從v1到v6的最短路。v1v2v3v4v6v5352242421

解（1）首先給v1以P標號，給其余所有點T標號。（2）*例一、用Dijkstra算法求下圖從v1到v6的8例一、用Dijkstra算法求下圖從v1到v6的最短路。v1v2v3v4v6v5352242421（4）*例一、用Dijkstra算法求下圖從v1到v6的9v1v2v3v4v6v5352242421（5）（6）反向追蹤得v1到v6的最短路為：*v1v2v3v4v6v5352242421（5）（6）反向追10237184566134105275934682求從1到8的最短路徑*237184566134105275934682求從1到8的11237184566134105275934682X={1}min{d12,d14,d16}=min{0+2,0+1,0+3}=min{2,1,3}=1X={1,4},p4=1p4=1p1=0*237184566134105275934682X={1}m12237184566134105275934682X={1,4}min{d12,d16,d42,d47}=min{0+2,0+3,1+10,1+2}=min{2,3,11,3}=2X={1,2,4},p2=2p1=0p4=1p2=2*237184566134105275934682X={1,413237184566134105275934682X={1,2,4}min{d16,d23,d25,d47}=min{0+3,2+6,2+5,1+2}=min{3,8,7,3}=3X={1,2,4,6},p6=3p2=2p4=1p1=0p6=3*237184566134105275934682X={1,214237184566134105275934682X={1,2,4,6}min{d23,d25,c47,d67}=min{2+6,2+5,1+2,3+4}=min{8,7,3,7}=3X={1,2,4,6,7},p7=3p2=2p4=1p1=0p6=3p7=3*237184566134105275934682X={1,215237184566134105275934682X={1,2,4,6,7}min{d23,d25,d75,d78}=min{2+6,2+5,3+3,3+8}=min{8,7,6,11}=6X={1,2,4,5,6,7},p5=6p2=2p4=1p1=0p6=3p7=3p5=6*237184566134105275934682X={1,216237184566134105275934682X={1,2,4,6,7}min{d23,d53,d58,d78}=min{2+6,6+9,6+4,3+8}=min{8,15,10,11}=8X={1,2,3,4,5,6,7},p3=8p2=2p4=1p1=0p6=3p7=3p5=6p3=8*237184566134105275934682X={1,217237184566134105275934682X={1,2,3,4,6,7}min{d38,d58,d78}=min{8+6,6+4,3+7}=min{14,10,11}=10X={1,2,3,4,5,6,7,8},p8=10p2=2p4=1p1=0p6=3p7=3p5=6p3=8p8=10*237184566134105275934682X={1,218237184566134105275934682X={1,2,3,4,6,7,8}1到8的最短路徑為{1，4，7，5，8}，長度為10。p2=2p4=1p1=0p6=3p7=3p5=6p3=8p8=10*237184566134105275934682X={1,219

最短路問題

*

最短路問題

*20一、問題的提法及應用背景

（1）問題的提法——尋求網(wǎng)絡中兩點間的最短路就是尋求連接這兩個點的邊的總權(quán)數(shù)最小的通路。（注意：在有向圖中，通路——開的初等鏈中所有的弧應是首尾相連的。）

（2）應用背景——管道鋪設(shè)、線路安排、廠區(qū)布局、設(shè)備更新等。*一、問題的提法及應用背景（1）問題的提法——尋求網(wǎng)絡中兩點21二、最短路算法

1．

D氏標號法（Dijkstra）；邊權(quán)非負2.列表法（福德法）；有負權(quán)，無負回路4v1v2v3v4v6v5v722561413412*二、最短路算法

1．D氏標號法（Dijkstra）；邊權(quán)非221．D氏標號法（Dijkstra）（1）求解思路——從始點出發(fā)，逐步順序地向外探尋，每向外延伸一步都要求是最短的。

（2）使用條件——網(wǎng)絡中所有的弧權(quán)均

非負，即。*1．D氏標號法（Dijkstra）（2）使用條件——網(wǎng)絡中所23（3）選用符號的意義：

①

P

標號（Permanent固定/永久性標號）——從始點到該標號點的最短路權(quán)②

T

標號（Temporary臨時性標號）——從始點到該標號點的最短路權(quán)上界*（3）選用符號的意義：*24（4）

計算步驟及例子：第一步：給起始點v1標上固定標號,其余各點標臨時性標號T(vj)=,j1;=l1j第二步：考慮滿足如下條件的所有點①與v1相鄰的點，即;②具有T標號，即，

為T

標號點集.

修改的T標號為，并將結(jié)果仍記為T(vj)。svj?若網(wǎng)絡圖中已無滿足此條件的T標號點，停止計算。*（4）

計算步驟及例子：第一步：給起始點v1標上固定標號25第三步：令,然后將的T標號改成P

標號，轉(zhuǎn)入第二步。此時，要注意將第二步中的改為。*第三步：令26例一、用Dijkstra算法求下圖從v1到v6的最短路。v1v2v3v4v6v5352242421

解（1）首先給v1以P標號，給其余所有點T標號。（2）*例一、用Dijkstra算法求下圖從v1到v6的27例一、用Dijkstra算法求下圖從v1到v6的最短路。v1v2v3v4v6v5352242421（4）*例一、用Dijkstra算法求下圖從v1到v6的28v1v2v3v4v6v5352242421（5）（6）反向追蹤得v1到v6的最短路為：*v1v2v3v4v6v5352242421（5）（6）反向追29237184566134105275934682求從1到8的最短路徑*237184566134105275934682求從1到8的30237184566134105275934682X={1}min{d12,d14,d16}=min{0+2,0+1,0+3}=min{2,1,3}=1X={1,4},p4=1p4=1p1=0*237184566134105275934682X={1}m31237184566134105275934682X={1,4}min{d12,d16,d42,d47}=min{0+2,0+3,1+10,1+2}=min{2,3,11,3}=2X={1,2,4},p2=2p1=0p4=1p2=2*237184566134105275934682X={1,432237184566134105275934682X={1,2,4}min{d16,d23,d25,d47}=min{0+3,2+6,2+5,1+2}=min{3,8,7,3}=3X={1,2,4,6},p6=3p2=2p4=1p1=0p6=3*237184566134105275934682X={1,233237184566134105275934682X={1,2,4,6}min{d23,d25,c47,d67}=min{2+6,2+5,1+2,3+4}=min{8,7,3,7}=3X={1,2,4,6,7},p7=3p2=2p4=1p1=0p6=3p7=3*237184566134105275934682X={1,234237184566134105275934682X={1,2,4,6,7}min{d23,d25,d75,d78}=min{2+6,2+5,3+3,3+8}=min{8,7,6,11}=6X={1,2,4,5,6,7},p5=6p2=2p4=1p1=0p6=3p7=3p5=6*237184566134105275934682X={1,2352371845