數(shù)據(jù)結構：最短路徑算法

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

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

All-PairsShortestpaths

（Floyd算法）

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

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

“最短路徑”=最小權路徑的權是路徑上所有邊的權之和。例：道路圖:從青島理工到金沙灘的最短路徑?2023/2/56v5v4v01005601010v1v2v3205030圖中從v0到其余各頂點之間的最短路徑: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貪心算法：

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

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

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

初始時,S僅包含源v0,

特殊路徑：

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

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

v1

v2

v3

v4

v5v0

v1

v2

v3

v4

v5權非負的單源最短路徑算法（Dijkstra）鄰接矩陣2023/2/511v0到其它各點的最短路

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

或者=<源點到其它頂點的路徑長度>+<其它頂點到頂點i的弧上的權值>

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

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

grap[maxn][maxn];//鄰接矩陣存儲圖int

pre[maxn];//標記這個點是否已經被選過intn,m;int

dist[maxn];//記錄從源點到其他所有點的最短距離2023/2/515voidinit()//對一些數(shù)據(jù)進行初始化{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++)//首先求出源點到其他所有點的距離

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算法，找到距離最短的那個點

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

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

pre[x]=1;

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

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++)//對有向圖進行存儲

{

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

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

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

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

2023/2/519例13226431104116023∞

0初始a：P=000000046602370a2=0411602370k=1a1=k=2k=30465023700-10P1=000000010002000010002300010P2=P3=a3=Floyd算法演示2023/2/520Floyd算法描述定義一個n階的方陣序列：A（-1），A（0）A（1）……A（n-1），其中：A（-1）[i][j]表示頂點vi到vj的直接邊長，A（-1）就是存儲圖的鄰接矩陣Edge[n][n]A（0）[i][j]表示從頂點vi到vj，中間頂點是v0的最短路徑長度A（1）[i][j]表示從頂點vi到vj，中間頂點序號不大于1的最短路徑長度………..A（k）[i][j]表示從頂點vi到vj，中間頂點序號不大于k的最短路徑長度..........2023/2/521A（n-1）[i][j]是最終求得的從頂點vi到vj的最短路徑長度增加中間頂點vk后，對于圖中的每一對頂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算法的代碼實現(xiàn)#include<iostream>#include<string.h>#include<stdio.h>#include<algorithm>#include<queue>usingnamespacestd;constintINF=0xfffffff;#definemaxn110int

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

dist[maxn][maxn];//記錄從所有點之間的最短距離2023/2/523voidinit()//對一些數(shù)據(jù)進行初始化{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++)//初始化，一開始每個點與點之間的路徑長度就等于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