大佬教程收集整理的这篇文章主要介绍了dijkstra算法求单源最短路径思路（图解），大佬教程大佬觉得挺不错的，现在分享给大家，也给大家做个参考。
思路概括
需要用到的数据结构:
一维数组dist[n]--根据下标存放源点到所有其他点的最短路径,
例如:dist[1]=10, 表示源点到达结点1的最短路径的长度为10
一维数组path[n]--根据下标存放某个点的前一个点的信息,这个点是所有能够到达该点中路径最短的一个点
例如:path[2]=3, 表示能够从结点3到达结点2,并且结点3到结点2的距离是所有到达结点2中最短的
一维标记数组S[n]--根据下标存放bool值,表示该点已经找到到达该点的最短路径
@H_672_4@minval--存放每一轮循环中dist[n]中最小的值,k--存放该最小值对应的结点思路:
从选取的源点求到其余所有n个点的最短路径,需要n次循环
每次循环找到某一个点的最短路径,重复n次就能找到源点到每一个结点的最短路径
具体看图:
循环结束时,dist就保存了源点到所有其他点的最短距离,path也保存好了直接前驱,通过适当的输出即可求出单源最短路径
代码如下:
点击查看代码
class Solution {
public:
void GetPath(vector<vector<int>>vec,int v0) {
int size = vec.size();
int S[MAX], k, minval;
vector<int>dist(sizE);//dist存放单源最短路径
vector<int>path(sizE);
//初始化
for (int i = 0; i < size; i++) {
dist[i] = vec[v0][i];
if (dist[i] != MAX)path[i] = v0;
else path[i] = -1;
}
S[v0] = 1;
dist[v0] = 0;
@R_696_9293@um = 1;
path[v0] = -1;
while (num < sizE) {
k = 0; minval = MAX;
for(int i=0;i<size;i++)
if ((dist[i] < minval) && (S[i] != 1)) {
minval = dist[i];
k = i;
}
S[k] = 1;
for(int i=0;i<size;i++)
if ( dist[k] + vec[k][i]<dist[i] ) {
dist[i] = dist[k] + vec[k][i];
path[i] = k;
}
num++;
}
cout<<"\n源点到各顶点的最短路径长和路径：";
for (int i = 0; i != size; i++) {
if (i == v0 )cout << "\n"<<dist[i]<< "\tpath:" << i << " <- " << v0;
else if (dist[i] == MAX)cout<<"\n无路径" << "\tpath:" << i << " <- " << v0;
else {
cout << "\n" << dist[i] << "\tpath:" << i << " ";
int pre = path[i];
while (pre != -1) {
cout << " <- " << pre << ' ';
pre = path[pre];
}
}
}
}
};
以上是大佬教程为你收集整理的dijkstra算法求单源最短路径思路（图解）全部内容，希望文章能够帮你解决dijkstra算法求单源最短路径思路（图解）所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错，欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。