dijkstar算法求单源最短路径
贪心算法
思路概括
需要用到的数据结构:
一维数组dist[n]--根据下标存放源点到所有其他点的最短路径,
例如:dist[1]=10, 表示源点到达结点1的最短路径的长度为10
一维数组path[n]--根据下标存放某个点的前一个点的信息,这个点是所有能够到达该点中路径最短的一个点
例如:path[2]=3, 表示能够从结点3到达结点2,并且结点3到结点2的距离是所有到达结点2中最短的
一维标记数组S[n]--根据下标存放bool值,表示该点已经找到到达该点的最短路径
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;
int num = 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];
}
}
}
}
};