C++如何實(shí)現(xiàn)最短路徑之Dijkstra算法

這篇文章給大家分享的是有關(guān)C++如何實(shí)現(xiàn)最短路徑之Dijkstra算法的內(nèi)容。小編覺(jué)得挺實(shí)用的，因此分享給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧。

網(wǎng)絡(luò)層的鏈路狀態(tài)路由選擇算法（LS算法），其中一種就是用Dijkstra算法寫(xiě)的。《算法導(dǎo)論》的介紹：Dijkstra算法解決的是帶權(quán)重的有向圖上單源最短路徑問(wèn)題，該算法要求所有邊的權(quán)重都為非負(fù)值。

算法思路

1. G集表示所有點(diǎn)集，S集表示已經(jīng)求解出源到某點(diǎn)的最短路徑的點(diǎn)集，V集表示為求出最短路徑的點(diǎn)集
2. 首先令S=?，V=G

如圖所示6個(gè)點(diǎn)8條邊  V={1,2,3,4,5,6}

1. 取u=1，把點(diǎn)1放入S中，S={1}   ,V={2,3,4,5,6}，遍歷與點(diǎn)1相連的點(diǎn)，并把權(quán)值放入數(shù)組
   

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

因?yàn)閐is[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中發(fā)現(xiàn)dis[3]為除dis[1],dis[2]外的最小值，所以令S=S∪{3}
   此時(shí)S={1,2,3},V={4,5,6}

因?yàn)閐is[5]=12>dis[3]+1=7+1    ?  令 dis[5]=dis[3]+1=7+1=8
因?yàn)閐is[6]=∞ >dis[3]+6=7+6     ?  令 dis[6]=dis[6]+6=7+6=13

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

因?yàn)閐is[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中發(fā)現(xiàn)dis[5]為除dis[1],dis[2],dis[3],dis[4]外的最小值，所以令S=S∪{5}
   此時(shí)S={1,2,3,4,5},V={6}

因?yàn)閐is[6]=12>dis[5]+2=8+2    ?  令 dis[6]=dis[5]+2=8+2=10

如上從點(diǎn)1到各個(gè)點(diǎn)的最短路徑就求出來(lái)，感覺(jué)最近寫(xiě)的很亂，不容易看懂。不過(guò)感謝各位看官能夠看到這兒。
關(guān)于n點(diǎn)m條邊求最短路徑，一般迭代n次就能得出所有點(diǎn)的最短路徑。
現(xiàn)在就是貼出代碼惹

/*
 * @author Wenpupil
 * @time  2019-04-04
 * @version 1.0
 * @Description 最短路徑之Dijkstra算法 關(guān)于無(wú)負(fù)權(quán)的無(wú)向圖練習(xí) 
 */
#include<iostream>
#include<cmath>
#include<string.h>
#define INIT  9999
using namespace std;
int map[20][20];              //存儲(chǔ)19個(gè)點(diǎn)的無(wú)向圖
int s[20];                    //標(biāo)記數(shù)組 
int dis[20];

void mDijkstra(int i,int m)
{
	for(int i=0;i<20;i++) 
		dis[i]=INIT;          //初始化dis數(shù)組 任務(wù)9999為路徑無(wú)窮大  
	memset(s,0,20);           //初始化標(biāo)記數(shù)組 
	
	dis[1]=0;                 //從1出發(fā)自身權(quán)為0 
	
	for(int i=1;i<=m;i++)     //m個(gè)點(diǎn) 進(jìn)行m次迭代 可以得到第m個(gè)點(diǎn)的最短路徑 
	{
		int weightSum=INIT;
		int u=0;
		for(int j=1;j<=m;j++)
		{
			if(!s[j]&&dis[j]<weightSum)
			{
			   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個(gè)點(diǎn)，n條邊
	cin>>m>>n;
	for(int i=0;i<n;i++)
	{
		int x,y,z;               //點(diǎn)X和點(diǎn)Y相連 之間權(quán)重為Z
		cin>>x>>y>>z;
		map[x][y]=map[y][x]=z;
	}
	mDijkstra(1,m);             //從節(jié)點(diǎn)1出發(fā) 遍歷全圖
	
	for(int i=1;i<=m;i++) cout<<dis[i]<<' ';  //顯示結(jié)果 
	return 0;
}

感謝各位的閱讀！關(guān)于C++如何實(shí)現(xiàn)最短路徑之Dijkstra算法就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，讓大家可以學(xué)到更多知識(shí)。如果覺(jué)得文章不錯(cuò)，可以把它分享出去讓更多的人看到吧！