最短路問(wèn)題迪杰斯特拉算法課件

最短路問(wèn)題

*

最短路問(wèn)題

*1一、問(wèn)題的提法及應(yīng)用背景

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

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

1．

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

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

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

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

①

P

標(biāo)號(hào)（Permanent固定/永久性標(biāo)號(hào)）——從始點(diǎn)到該標(biāo)號(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)上界*（3）選用符號(hào)的意義：*5（4）

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

為T

標(biāo)號(hào)點(diǎn)集.

修改的T標(biāo)號(hào)為，并將結(jié)果仍記為T(vj)。svj?若網(wǎng)絡(luò)圖中已無(wú)滿足此條件的T標(biāo)號(hào)點(diǎn)，停止計(jì)算。*（4）

計(jì)算步驟及例子：第一步：給起始點(diǎn)v1標(biāo)上固定標(biāo)號(hào)6第三步：令,然后將的T標(biāo)號(hào)改成P

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

解（1）首先給v1以P標(biāo)號(hào)，給其余所有點(diǎn)T標(biāo)號(hào)。（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}，長(zhǎng)度為10。p2=2p4=1p1=0p6=3p7=3p5=6p3=8p8=10*237184566134105275934682X={1,219

最短路問(wèn)題

*

最短路問(wèn)題

*20一、問(wèn)題的提法及應(yīng)用背景

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

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

1．

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

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

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

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

①

P

標(biāo)號(hào)（Permanent固定/永久性標(biāo)號(hào)）——從始點(diǎn)到該標(biāo)號(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)上界*（3）選用符號(hào)的意義：*24（4）

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

為T

標(biāo)號(hào)點(diǎn)集.

修改的T標(biāo)號(hào)為，并將結(jié)果仍記為T(vj)。svj?若網(wǎng)絡(luò)圖中已無(wú)滿足此條件的T標(biāo)號(hào)點(diǎn)，停止計(jì)算。*（4）

計(jì)算步驟及例子：第一步：給起始點(diǎn)v1標(biāo)上固定標(biāo)號(hào)25第三步：令,然后將的T標(biāo)號(hào)改成P

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

解（1）首先給v1以P標(biāo)號(hào)，給其余所有點(diǎn)T標(biāo)號(hào)。（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