C++ DijkStra最短路径（输出两点间最短路径与线路) - 好文

因为Dijkstra迪杰斯特拉算法每次都是从当前点计算出到所有相邻且未访问过的点的距离，再从中选出距离最小的点加入变成已访问。所以该思想类似于广度优先遍历BFS。

参考链接如下:

（1）图算法之最短路径（Dijkstra） <https://www.cnblogs.com/nigang/p/3658990.html>

（2）DijkStra最短路径的C++实现与输出路径
<https://blog.csdn.net/u012577585/article/details/45030773>

(3) 柳诺-【最短路径】之Dijkstra算法 <https://www.liuchuo.net/archives/2357>

（4） DijkStra最短路径的C++实现与输出路径
<https://blog.csdn.net/u012577585/article/details/45030773>

实现:

代码如下：
/*输入: 5 6 0 0 1 1 0 2 2 0 3 1 1 2 1 2 4 1 3 4 1 或 6 9 0 0 1 1 0 2 12 1 2 9 1
3 3 2 4 5 3 2 4 3 4 13 3 5 15 4 5 4 */ #include <iostream> #include <algorithm>
#include <stack> using namespace std; #define N 520 int
edge[N][N],weight[N],disp[N]; bool visited[N] = {false}; const int inf =
999999; int main(){ int prev[N];//用来标注当前结点的上一个结点，以便输出两点间最短路线
fill(edge[0],edge[0] + N * N,inf);//注意这里要是N*N，要不然不是全部 fill(disp,disp + N,inf);
int n,m;//对应城市数，城市之间连线数 cin>>n>>m; int start_point; cin>>start_point;//输入起点城市
int a,b,c; for(int i=0;i < m;i++) { cin>>a>>b>>c; edge[a][b] = edge[b][a] = c;
} for(int i=0;i<N;i++){ prev[i] = i;//初始状态设每个点的前驱为自身 edge[i][i] = 0; }
disp[start_point] = 0; for(int i = 0;i < n;i++){ int u = -1,min = inf; for(int
j = 0;j < n;j++){ if(visited[j] == false && disp[j] <= min) { u = j; min =
disp[j]; } } if(u == -1) break; visited[u] = true; for(int v = 0;v < n;v++){
if(visited[v] == false && edge[u][v] != inf) { if(disp[u] + edge[u][v] <
disp[v]){ disp[v] = disp[u] + edge[u][v]; prev[v] =
u;//prev保存当前结点的上一个节点，以便输出最短路线 cout<<v<<" "<<prev[v]<<endl; } } } }
//显示起点到各个点的最短路径 for (int i=0;i<n;i++) {
cout<<"起点"<<start_point<<"到"<<i<<"的最短距离为: "<<disp[i]<<endl; } //显示起到到某个点的线路
int end_point;//终点 cout<<"请输入终点:"; cin>>end_point; stack<int> myStack; int
temp = end_point; myStack.push(end_point);//先加终点 while(start_point != temp){
temp = prev[temp]; myStack.push(temp);//注意这里是把当前点的上一个结点放进去，此时换成了temp }
cout<<"起点"<<start_point<<"到"<<end_point<<"的最短路线为: "; while(!myStack.empty()){
cout<<myStack.top()<<" "; myStack.pop(); } return 0; }

热门工具换一换