Dijkstra算法（记录路径） - 好文

与求最短路相比，增加一个path数组，来记录最短路的路径

先将path[i]=-1，之后每次找出最短路的点p后将path[j]=p

用path[j]=i表示从i到j最短路的路径
for(int j=1; j<=n; j++){ if(!visited[j] && dis[p]+mapp[p][j]<dis[j]){
dis[j]=dis[p]+mapp[p][j]; path[j]=p; } }

1339: 单源最短路径

时间限制: 1 Sec 内存限制: 128 MB
提交: 4 解决: 3
[提交 <http://exam.upc.edu.cn/submitpage.php?id=1339>][状态
<http://exam.upc.edu.cn/problemstatus.php?id=1339>][讨论版
<http://exam.upc.edu.cn/bbs.php?pid=1339>][命题人:外部导入]

题目描述

给定带权有向图G=（V,E)，其中每条边的权是非负数。另外，还给定V中的一个顶点，称为源。现在要计算从源到所有其他各顶点的最短路径长度，这里路径的长度是指路径上各边权之和。这个问题通常称为单源最短路径问题（Single-Source
Shortest Paths)。
如下图所示，就是要计算源点V1到其他各个顶点的最短距离，并输出相应的路径。

输入

本题有多组数据，第1行有2个数据n和m，其中n表示结点的个数，m表示路径的数目。

接下来有m行，每行有3个数据s,t和edge，其中s表示路径的起点，t表示路径的终点，edge表示该路径的长度。

当n=0，m=0时，输入数据结束。

输出

源点（统一规定为v1）到所有其他各定点的最短路径长度。

接下来有n-1行，是从各个定点（按升序）回到源点的路径。

样例输入
5 7 1 2 10 1 4 25 1 5 80 2 3 40 3 5 10 4 3 20 4 5 50 0 0
样例输出
10 45 25 55 2-->1 3-->4-->1 4-->1 5-->3-->4-->1

代码：
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int
maxx = 999999999; const int INF = 1e3 + 100; int n, m; int mapp[INF][INF]; int
dis[INF]; int path[INF]; bool visited[INF]; void Dijkstra(int v0) { for (int i
= 1; i <= n; i++) { dis[i] = mapp[v0][i]; visited[i] = 0; path[i] = -1; }
visited[v0] = 1; for (int i = 1; i <= n; i++) { int p, minn = maxx; for (int j
= 1; j <= n; j++) { if (!visited[j] && dis[j] < minn) { p = j; minn = dis[j]; }
} visited[p] = 1; for (int j = 1; j <= n; j++) { if (!visited[j] && dis[p] +
mapp[p][j] < dis[j]) { dis[j] = dis[p] + mapp[p][j]; path[j] = p; } } } return;
} int main() { while (cin >> n >> m) { if (n == 0 && m == 0) break; for (int i
= 0; i <= n; i++) { for (int j = 0; j <= n; j++) { mapp[i][j] = maxx; } } int
s, t, d; while (m--) { cin >> s >> t >> d; mapp[s][t] = d; } Dijkstra(1); for
(int i = 2; i <= n; i++) { if (i == 2) cout << dis[i]; else cout << " " <<
dis[i]; } cout << endl; for (int i = 2; i <= n; i++) { cout << i; int p = i;
while (path[p] != -1) { cout << "-->" << path[p]; p = path[p]; } cout << "-->"
<< "1" << endl; } } return 0; }
该代码输出是倒序

如果要正序输出，可以使用栈记录，然后再输出
void print(int s,int n) { stack<int> q; for(int i=2;i<=n;i++) { int p=i;
while(path[p]!=-1) { q.push(p); p=path[p]; } q.push(p); cout<<s<<"-->"<<i<<" ";
cout<<"dis"<<":"<<dis[i]<<" "; cout<<s; while(!q.empty()) {
cout<<"-->"<<q.top(); q.pop(); } cout<<endl; } }
输出格式为：

热门工具换一换