本文转载自我在 CSDN 的旧博客:算法——最短路径之 Dijkstra(写于 2018-03-24),迁移时整理了格式。
解决非负权边的最短路径问题时,Dijkstra 算法还是不错的
不多 bb,挂模板代码
没写注释,很好理解的
#include <cstdio>
#include <iostream>
#include <cstring>
#include <stack>
using namespace std;
const int N = 100;
const int INF = 1e7;
int map[N][N],dist[N],p[N],n,m;
bool flag[N];
void Dijkstra(int u)
{
for(int i = 1; i <= n; i++)
{
dist[i] = map[u][i];
flag[i] = false;
if(dist[i] == INF)
{
p[i] = -1;
}
else
{
p[i] = u;
}
}
dist[u] = 0;
flag[u] = true;
for(int i = 1; i <= n; i++)
{
int temp = INF, t = u;
for(int j = 1; j <= n; j++)
{
if(!flag[j] && dist[j] < temp)
{
t = j;
temp = dist[j];
}
}
if(t == u)
{
return;
}
flag[t] = true;
for(int j = 1; j <= n; j++)
{
if(!flag[j] && map[t][j] < INF)
{
if(dist[j] > dist[t] + map[t][j])
{
dist[j] = dist[t] + map[t][j];
p[j] = t;
}
}
}
}
}
void findPath(int u)
{
int x;
stack<int>s;
cout << "源点为 : " << u << endl;
for(int i = 1; i <= n; i++)
{
x = p[i];
while(x != -1)
{
s.push(x);
x = p[x];
}
cout << "最短路径为 : ";
while(!s.empty())
{
cout << s.top() << "->";
s.pop();
}
cout << i << ", 最短距离为 : " << dist[i] <<endl;
}
}
int main()
{
int u,v,w,st;
cout << "请输入节点个数 通路个数" << endl;
cin >> n >> m;
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= n; j++)
{
map[i][j] = INF;
}
}
cout << "请输入三个数 u v w 代表从u到v到的路径为w" << endl;
for(int i = 1; i <= m; i++)
{
cin >> u >> v >> w;
map[u][v] = min(map[u][v], w);
}
cout << "请输入初始节点" << endl;
cin >> st;
Dijkstra(st);
// for(int i = 1; i <= n; i++){
// cout << st << "->" << i << endl;
// if(dist[i] == INF){
// cout << "没有路可以走." << endl;
// }else{
// cout << "最短路径为 : " << dist[i] << endl;
// }
// }
findPath(st);
return 0;
}
留言