5-5最短路徑v第五章圖最短路徑的定義最短路徑：非帶權(quán)圖——邊數(shù)最少的路徑v0到v4的最短路徑：v0v4：1v0v3v4：2v0v1v2v4：3v0v3v2v4：3v0v2v3v4v1最短路徑：帶權(quán)圖——邊上的權(quán)值之和最少的路徑101003050201060v0到v4的最短路徑：v0v4：100v0v3v4：90v0v1v2v4：70v0v3v2v4：60v0v2v3v4v1對于非帶權(quán)圖，如何求最短路徑？廣度優(yōu)先遍歷v0v1v4v0v1廣度優(yōu)先遍歷序列：level=01101003050201060對于帶權(quán)圖，如何求最短路徑？最短路徑的定義Dijkstra算法Floyd算法學(xué)什么？5-5-1Dijkstra算法v第五章圖單源點最短路徑問題【問題】給定帶權(quán)有向圖G＝(V,E)和源點v∈V，求從v到G中其余各頂點的最短路徑

【想法】。。。。。?！舅惴ā緿ijstra算法應(yīng)用實例——計算機網(wǎng)絡(luò)傳輸?shù)膯栴}：怎樣找到一種最經(jīng)濟的方式，從一臺計算機向網(wǎng)上所有其它計算機發(fā)送一條消息v0v2v3v4v1101003050201060基本思想v：源點S：已經(jīng)生成最短路徑的終點w<v,vi>：從頂點v到頂點vi

的權(quán)值dist(v,vi)：表示從頂點v

到頂點vi

的最短路徑長度算法：Dijkstra算法輸入：有向網(wǎng)圖

G=(V，E)，源點

v

輸出：從

v到其他所有頂點的最短路徑1.初始化：集合S={v}；dist(v,vi)=w<v,vi>,(i=1...n)；2.重復(fù)下述操作直到S==V2.1dist(v,vk)=min{dist(v,vj),(j=1..n)}；

2.2S=S+{vk}；

2.3dist(v,vj)=min{dist(v,vj),dist(v,vk)+w<vk,vj>}；vivS

V-Svk當(dāng)前生長點算法：Dijkstra算法輸入：有向網(wǎng)圖

G=(V，E)，源點

v

輸出：從

v到其他所有頂點的最短路徑1.初始化：集合S={v}；dist(v,vi)=w<v,vi>,(i=1...n)；2.重復(fù)下述操作直到S==V2.1dist(v,vk)=min{dist(v,vj),(j=1..n)}；

2.2S=S+{vk}；

2.3dist(v,vj)=min{dist(v,vj),dist(v,vk)+w<vk,vj>}；圖采用什么存儲結(jié)構(gòu)呢？鄰接矩陣存儲結(jié)構(gòu)算法：Dijkstra算法輸入：有向網(wǎng)圖

G=(V，E)，源點

v

輸出：從

v到其他所有頂點的最短路徑1.初始化：集合S={v}；dist(v,vi)=w<v,vi>,(i=1...n)；2.重復(fù)下述操作直到S==V2.1dist(v,vk)=min{dist(v,vj),(j=1..n)}；

2.2S=S+{vk}；

2.3dist(v,vj)=min{dist(v,vj),dist(v,vk)+w<vk,vj>}；如何存儲dist(v,vi)呢？

待定路徑表（當(dāng)前的最短路徑）

整型數(shù)組dist[n]：存儲當(dāng)前最短路徑的長度

字符串?dāng)?shù)組path[n]：存儲當(dāng)前的最短路徑，即頂點序列存儲結(jié)構(gòu)v0v2v3v4v1101003050201060當(dāng)前的最短路徑：<v0,v1>10<v0,v2>∞<v0,v3>30<v0,v4>100v0v2v3v4v11010030∞010∞30100dist[n]

運行實例v0v2v3v4v1101003050201060當(dāng)前的最短路徑：<v0,v1,v2>60<v0,v3>30<v0,v4>100v0v2v3v4v11010030∞50010∞30100dist[n]

0106030100dist[n]

運行實例當(dāng)前生長點：v1v0v2v3v4v11010030∞v0v2v3v4v1101003050201060當(dāng)前的最短路徑：<v0,v3,v2>50<v0,v3,v4>90v0v2v3v4v11030當(dāng)前的最短路徑：<v0,v3,v2,v4>60v0v2v3v4v11030602020105010060010503090dist[n]

010503060dist[n]

運行實例當(dāng)前生長點：v3當(dāng)前生長點：v2v0v2v3v4v1101003050201060voidDijkstra(intv)/*從源點v出發(fā)*/{inti,k,num,dist[MaxSize];stringpath[MaxSize];for(i=0;i<vertexNum;i++)/*初始化數(shù)組dist[n]和path[n]*/{dist[i]=edge[v][i];path[i]=vertex[v]+vertex[i];/*字符串連接*/}v0distpath下標(biāo)1234終點

v1

v2

v3

v4

S10v0,v1∞v0,v230v0,v3100v0,v4算法實現(xiàn)v0v2v3v4v1101003050201060v0distpath下標(biāo)1234終點

v1

v2

v3

v4

Sdistpathdistpathdistpathdistpath10v0,v1∞v0,v230v0,v3100v0,v4for(num=1;num<vertexNum;num++){}for(k=0,i=0;i<vertexNum;i++)

if((dist[i]!=0)&&(dist[i]<dist[k]))k=i;cout<<path[k]<<dist[k];v0,v1算法實現(xiàn)v0v2v3v4v1101003050201060v0distpath下標(biāo)1234終點

v1

v2

v3

v4

Sdistpathdistpathdistpathdistpath10v0,v1∞v0,v230v0,v3100v0,v4v0,v10v0,v160

v0,v1,v230v0,v3100v0,v4for(num=1;num<vertexNum;num++){}for(i=0;i<vertexNum;i++)if(dist[i]>dist[k]+edge[k][i]){dist[i]=dist[k]+edge[k][i];path[i]=path[k]+vertex[i];}dist[k]=0;算法實現(xiàn)v0distpath下標(biāo)1234終點

v1

v2

v3

v4

Sdistpathdistpathdistpathdistpath10v0,v1∞v0,v230v0,v3100v0,v40v0,v160

v0,v1,v230v0,v3100v0,v4v0,v1v0,v2,v350

v0,v3,v20v0,v390v0,v3,v4v0,v1,v3,v20

v0,v3,v260v0,v3,v2,v4v0,v1,v3,v2,v40v0,v3,v2,v4v0v2v3v4v1101003050201060驗證算法voidDijkstra(intv)/*從源點v出發(fā)*/{inti,k,num,dist[MaxSize];stringpath[MaxSize];

for(i=0;i<vertexNum;i++){dist[i]=edge[v][i];path[i]=vertex[v]+vertex[i];}}

for(num=1;num<vertexNum;num++){

for(k=0,i=0;i<vertexNum;i++)

if((dist[i]!=0)&&(dist[i]<dist[k]))k=i;cout<<path[k]<<dist[k];

}O(n)時間復(fù)雜度？O(n2)O(n)O(n)

for(i=0;i<vertexNum;i++)if(dist[i]>dist[k]+edge[k][i]){dist[i]=dist[k]+edge[k][i];path[i]=path[k]+vertex[i];}dist[k]=0;O(n)算法實現(xiàn)5-5-2Floyd算法v第五章圖每一對頂點的最短路徑問題【問題】給定帶權(quán)有向圖G＝(V,E)，對任意頂點

vi

和vj（i≠

j），求從頂點

vi到頂點

vj的最短路徑【想法1】每次以一個頂點為源點調(diào)用Dijkstra算法。顯然，時間復(fù)雜度為O(n3)

【算法】Floyd算法【想法2】

。。。。。。算法：Floyd算法輸入：帶權(quán)有向圖

G=(V，E)輸出：每一對頂點的最短路徑

1.初始化：假設(shè)從

vi到

vj的弧是最短路徑，即dist-1(vi,vj)=w<vi,vj>；2.循環(huán)變量k

從0~n-1進行n次迭代：distk(vi,vj)=min{distk-1(vi,vj),distk-1(vi,vk)+distk-1(vk,vj)}w<vi,vj>：從頂點vi到頂點vj

的權(quán)值distk(vi,vj)：從頂點vi

到頂點vj

經(jīng)過的頂點編號不大于k的最短路徑長度vivjvk基本思想如何存儲dist？如何存儲帶權(quán)有向圖？鄰接矩陣算法：Floyd算法輸入：帶權(quán)有向圖

G=(V，E)輸出：每一對頂點的最短路徑

1.初始化：假設(shè)從

vi到

vj的弧是最短路徑，即dist-1(vi,vj)=w<vi,vj>；2.循環(huán)變量k

從0~n-1進行n次迭代：

distk(vi,vj)=min{distk-1(vi,vj),distk-1(vi,vk)+distk-1(vk,vj)}dist-1(vi,vj)=w<vi,vj>distk(vi,vj)=min{distk-1(vi,vj),distk-1(vi,vk)+distk-1(vk,vj)}存儲結(jié)構(gòu)初始化dist-1

=04116023∞0voidFloyd(){inti,j,k,dist[MaxSize][MaxSize];for(i=0;i<vertexNum;i++)for(j=0;j<vertexNum;j++)dist[i][j]=edge[i][j];}運行實例v0v2v1346112經(jīng)過v0dist0

=0411602370經(jīng)過v1dist1

=046602370經(jīng)過