用C++實現最短路徑之Dijkstra算法

網絡層的鏈路狀態路由選擇算法（LS算法），其中一種就是用Dijkstra算法寫的。《算法導論》的介紹：Dijkstra算法解決的是帶權重的有向圖上單源最短路徑問題，該算法要求所有邊的權重都為非負值。

算法思路

1. G集表示所有點集，S集表示已經求解出源到某點的最短路徑的點集，V集表示為求出最短路徑的點集
2. 首先令S=Ø，V=G

如圖所示6個點8條邊 V={1,2,3,4,5,6}

1. 取u=1，把點1放入S中，S={1} ,V={2,3,4,5,6}，遍歷與點1相連的點，並把權值放入數組

4.由路徑數組可得知此時V集中 點2有最短路徑（值為3）所以令u=2，則S={1,2} ,V={3,4,5,6}

因為dis[3]=dis[2]+4 7=3+4

… . dis[5]=dis[2]+9 12=3+9

1. 同理如今S={1,2},V={3,4,5,6},在V中發現dis[3]為除dis[1],dis[2]外的最小值，所以令S=S∪{3}
2. 此時S={1,2,3},V={4,5,6}

因為dis[5]=12>dis[3]+1=7+1 令 dis[5]=dis[3]+1=7+1=8

因為dis[6]=∞ >dis[3]+6=7+6 令 dis[6]=dis[6]+6=7+6=13

1. 同理如今S={1,2,3},V={4,5,6},在V中發現dis[4]為除dis[1],dis[2],dis[3]外的最小值，所以令S=S∪{4}
2. 此時S={1,2,3,4},V={5,6}

因為dis[6]=13>dis[4]+7=5+7 令 dis[6]=dis[4]+7=5+7=12

1. 同理如今S={1,2,3,4},V={5,6},在V中發現dis[5]為除dis[1],dis[2],dis[3],dis[4]外的最小值，所以令S=S∪{5}
2. 此時S={1,2,3,4,5},V={6}

因為dis[6]=12>dis[5]+2=8+2 令 dis[6]=dis[5]+2=8+2=10

如上從點1到各個點的最短路徑就求出來，感覺最近寫的很亂，不容易看懂。不過感謝各位看官能夠看到這兒。

關於n點m條邊求最短路徑，一般疊代n次就能得出所有點的最短路徑。

現在就是貼出代碼惹

/*

* @author Wenpupil

* @time 2019-04-04

* @version 1.0

* @Description 最短路徑之Dijkstra算法 關於無負權的無向圖練習

*/

#include

#include

#include

#define INIT 9999

using namespace std;

int map[20][20]; //存儲19個點的無向圖

int s[20]; //標記數組

int dis[20];

void mDijkstra(int i,int m)

{

for(int i=0;i<20;i++)

dis[i]=INIT; //初始化dis數組 任務9999為路徑無窮大

memset(s,0,20); //初始化標記數組

dis[1]=0; //從1出發自身權為0

for(int i=1;i<=m;i++) //m個點 進行m次疊代 可以得到第m個點的最短路徑

{

int weightSum=INIT;

int u=0;

for(int j=1;j<=m;j++)

{

if(!s[j]&&dis[j]

{

weightSum=dis[j];

u=j;

}

}

s[u]=1;

for(int j=1;j<=m;j++)

{

if(!s[j]&&map[u][j]>0){

dis[j]=min(dis[j],dis[u]+map[u][j]);

}

}

}

}

int main(void)

{

int m,n; //共有m個點，n條邊

cin>>m>>n;

for(int i=0;i

{

int x,y,z; //點X和點Y相連 之間權重為Z

cin>>x>>y>>z;

map[x][y]=map[y][x]=z;

}

mDijkstra(1,m); //從節點1出發 遍歷全圖

for(int i=1;i<=m;i++) cout<

return 0;

}

【推薦課程：C++視頻教程】

以上就是用C++實現最短路徑之Dijkstra算法的詳細內容，更多請關注其它相關文章！

更多技巧請《轉發 + 關注》哦！