數(shù)據(jù)結(jié)構(gòu)：最短路徑算法

圖算法（二）最短路經(jīng)ShortestPath青島理工大學(xué)acm2023/2/51Dijkstra算法練習(xí)題鏈接/vjudge/contest/view.action?cid=29337#overviewFloyd算法練習(xí)題鏈接/vjudge/contest/view.action?cid=29305#overview密碼都是：6712023/2/52/sjjg/DataStructure/DS/web/flashhtml/Dijkstra.htm這個(gè)鏈接是Dijskra算法的動(dòng)態(tài)演示2023/2/53問題:兩地之間是否有通路?若存在多條通路，哪條路最短？最短路徑問題2023/2/54單源最短路徑

Single-SourceShortestPath(Dijkstra算法)所有頂點(diǎn)對(duì)間的最短路徑問題

All-PairsShortestpaths

（Floyd算法）

最短路徑問題2023/2/55單源最短路徑

Single-SourceShortestPath問題:帶權(quán)有向圖G（E,V),找出從給定源頂點(diǎn)s到其它頂點(diǎn)v的權(quán)最小路徑。

“最短路徑”=最小權(quán)路徑的權(quán)是路徑上所有邊的權(quán)之和。例：道路圖:從青島理工到金沙灘的最短路徑?2023/2/56v5v4v01005601010v1v2v3205030圖中從v0到其余各頂點(diǎn)之間的最短路徑:v0到v1無

v0到

v2(v0,v2)10v0到

v3(v0,v4,

v3)50v0到

v4(v0,v4)30v0到

v5(v0,v4,

v3,v5)60單源最短路徑2023/2/57貪心算法：

若頂點(diǎn)序列{V0,V1,…,Vn}是從V0到Vn的最短路，則序列{V0,V1,…,Vn-1}必為從V0到Vn-1的最短路。權(quán)非負(fù)的單源最短路徑算法（Dijkstra）2023/2/58基本思想：將圖中所有頂點(diǎn)分成兩組:S,V-S

一組是包括已確定最短路徑的頂點(diǎn)的集合S，另一組是尚未確定的最短路徑的頂點(diǎn)集V-S。

S初始僅包含源v0,不斷在V-S做貪心選擇擴(kuò)充集合S。權(quán)非負(fù)的單源最短路徑算法（Dijkstra）2023/2/59權(quán)非負(fù)的單源最短路徑算法（Dijkstra）

初始時(shí),S僅包含源v0,

特殊路徑：

從源到G中某一頂點(diǎn)u且中間只經(jīng)過S中頂點(diǎn)的路稱為從源到u的特殊路徑。步驟:(1)取v0加入S中

(2)從V-S中取出具有當(dāng)前最短路徑長度的頂點(diǎn)w加入S中。2023/2/510v5v4v0100601010v1v3205030v2v0

v1

v2

v3

v4

v5v0

v1

v2

v3

v4

v5權(quán)非負(fù)的單源最短路徑算法（Dijkstra）鄰接矩陣2023/2/511v0到其它各點(diǎn)的最短路

i=1i=2i=3i=4i=5初始時(shí)v0∞10∞30100v2∞10∞30100v4∞10503090v3∞30503060v5∞30503060v1∞305030602023/2/512Dijkstra算法：一般情況下，Dist[k]=<源點(diǎn)到頂點(diǎn)i的弧上的權(quán)值>

或者=<源點(diǎn)到其它頂點(diǎn)的路徑長度>+<其它頂點(diǎn)到頂點(diǎn)i的弧上的權(quán)值>

設(shè)置輔助數(shù)組Dist，其中每個(gè)分量Dist[i]表示

當(dāng)前所求得的從源點(diǎn)到其余各頂點(diǎn)i的最短路徑的長度。2023/2/5131）在所有從源點(diǎn)出發(fā)的弧中選取一條權(quán)值最小的弧，即為第一條最短路徑。2）修改其它各頂點(diǎn)的Dist[i]值。假設(shè)求得最短路徑的頂點(diǎn)為u，若Dist[u]+G.arcs[u][i]<Dist[i]則將Dist[i]改為Dist[u]+G.arcs[u][i]V0和i之間存在弧V0和i之間不存在弧其中的最小值即為最短路徑的長度。2023/2/514權(quán)非負(fù)的單源最短路徑算法（Dijkstra）#include<iostream>#include<string.h>#include<stdio.h>usingnamespacestd;constintINF=0xfffffff;#definemaxn110int

grap[maxn][maxn];//鄰接矩陣存儲(chǔ)圖int

pre[maxn];//標(biāo)記這個(gè)點(diǎn)是否已經(jīng)被選過intn,m;int

dist[maxn];//記錄從源點(diǎn)到其他所有點(diǎn)的最短距離2023/2/515voidinit()//對(duì)一些數(shù)據(jù)進(jìn)行初始化{inti,j;

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

grap[i][j]=INF;

memset(pre,0,sizeof(pre));}voiddijkstra(intu){

inti,j;

for(i=1;i<=n;i++)//首先求出源點(diǎn)到其他所有點(diǎn)的距離

dist[i]=grap[u][i];

pre[u]=1;2023/2/516

intx=u;

for(i=1;i<n-1;i++) {int

maxs=INF;

for(j=1;j<=n;j++)//類似于最小生成樹prim算法，找到距離最短的那個(gè)點(diǎn)

if(!pre[j]&&maxs>dist[j]) {

maxs=dist[j]; x=j; }

pre[x]=1;

for(j=1;j<=n;j++)//然后再通過這個(gè)點(diǎn)去得到其他點(diǎn)的最短距離

if(!pre[j]&&dist[j]>(dist[x]+grap[x][j])&&grap[x][j]<INF)

dist[j]=grap[x][j]+dist[x]; }}2023/2/517intmain(){

scanf("%d%d",&n,&m); init();

inti,x,y,z;

for(i=0;i<m;i++)//對(duì)有向圖進(jìn)行存儲(chǔ)

{

scanf("%d%d%d",&x,&y,&z);

grap[x][y]=z; } dijkstra(1);//假設(shè)求點(diǎn)1到其他點(diǎn)的最短路

return0;}2023/2/518所有頂點(diǎn)對(duì)之間的最短路徑算法Floyd算法已知一個(gè)有向圖（無向圖），對(duì)于每對(duì)頂點(diǎn)Vi！=Vj

，求出它們之間的最短路徑長度。解決這個(gè)問題有兩種方法：（1）輪流以每個(gè)頂點(diǎn)為源點(diǎn)重復(fù)執(zhí)行dijkstra算法。（2）采用Floyd算法，時(shí)間復(fù)雜度O（n3）

2023/2/519例13226431104116023∞

0初始a：P=000000046602370a2=0411602370k=1a1=k=2k=30465023700-10P1=000000010002000010002300010P2=P3=a3=Floyd算法演示2023/2/520Floyd算法描述定義一個(gè)n階的方陣序列：A（-1），A（0）A（1）……A（n-1），其中：A（-1）[i][j]表示頂點(diǎn)vi到vj的直接邊長，A（-1）就是存儲(chǔ)圖的鄰接矩陣Edge[n][n]A（0）[i][j]表示從頂點(diǎn)vi到vj，中間頂點(diǎn)是v0的最短路徑長度A（1）[i][j]表示從頂點(diǎn)vi到vj，中間頂點(diǎn)序號(hào)不大于1的最短路徑長度………..A（k）[i][j]表示從頂點(diǎn)vi到vj，中間頂點(diǎn)序號(hào)不大于k的最短路徑長度..........2023/2/521A（n-1）[i][j]是最終求得的從頂點(diǎn)vi到vj的最短路徑長度增加中間頂點(diǎn)vk后，對(duì)于圖中的每一對(duì)頂vi和vj，要比較從vi到vk的最短路徑長度加上從vk到vj的最短路徑長度是否小于原來從vi到vj的最短路徑長度，即比較A（k-1）[i][k]+A（k-1）[k][j]與A（k-1）[i][j]的大小，去較小的為A（k-1）[i][j]的值。因此我們得到遞推公式為：2023/2/522Floyd算法的代碼實(shí)現(xiàn)#include<iostream>#include<string.h>#include<stdio.h>#include<algorithm>#include<queue>usingnamespacestd;constintINF=0xfffffff;#definemaxn110int

grap[maxn][maxn];//鄰接矩陣存儲(chǔ)圖intn,m;int

dist[maxn][maxn];//記錄從所有點(diǎn)之間的最短距離2023/2/523voidinit()//對(duì)一些數(shù)據(jù)進(jìn)行初始化{inti,j;

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

grap[i][j]=INF;}voidfloyd(){inti,j,k;

for(i=1;i<=n;i++)//初始化，一開始每個(gè)點(diǎn)與點(diǎn)之間的路徑長度就等于grap中的長度

for(j=1;j<=n;j++)

dist[i][j]=grap[i][j];

for(k=1;k<=n;k++)

for(i=1;i<=n;i++)

for(j=1;j<=n;j++) {if(k==i||k==j)continue;

if(dist[i][k]+dist[k][j]<dist[i][j])

dist[i][j]=dist[i][k]+dist[k][j]; }}2023/2/524intmain(){

scanf("%d%d",&n,&m); init();

inti,x,y,z