这篇文章给大家分享的是有关C++如何实现最短路径之Dijkstra算法的内容。小编觉得挺实用的,因此分享给大家做个参考。一起跟随小编过来看看吧。
网络层的链路状态路由选择算法(LS算法),其中一种就是用Dijkstra算法写的。《算法导论》的介绍:Dijkstra算法解决的是带权重的有向图上单源最短路径问题,该算法要求所有边的权重都为非负值。
算法思路
如图所示6个点8条边 V={1,2,3,4,5,6}
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
因为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
因为dis[6]=13>dis[4]+7=5+7 ⇒ 令 dis[6]=dis[4]+7=5+7=12
因为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<iostream>
#include<cmath>
#include<string.h>
#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)
{
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<n;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<<dis[i]<<' '; //显示结果
return 0;
}
感谢各位的阅读!关于C++如何实现最短路径之Dijkstra算法就分享到这里了,希望以上内容可以对大家有一定的帮助,让大家可以学到更多知识。如果觉得文章不错,可以把它分享出去让更多的人看到吧!
亿速云「云服务器」,即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘,价格低至29元/月。点击查看>>
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。