5 7 1 2 3 1 3 5 2 3 10 2 4 4 2 5 1 3 4 5 4 5 1
①
通过一个pre数组来记录路径，pre[i, j]的值如果为p，就表示i到j的最短行经为 i->...->p->j，也就是说pre[i, j]的值p是i到j的最短行径中的j之前的最后一个点。pre数组的初值为pre[i, j] = i。有了这个数组之后，要找最短路径就轻而易举了。对于i到j而言找出pre[i, j]，令其值为p，就知道了路径 i->...->p->j；再去找pre[i, p]，令其值为q，i到p的最短路径为 i->...->q->p；再去找pre[i, q]，令其值为r，i到q的最短路径为 i->...->r->q；所以一再反复，到了某个pre[i, t]的值为i时，就表示i到t的最短路径为 i->t，此时就得到答案了，i到j的最短行径为 i->t->...->q->p->j。因为上述的算法是从终点到起点的顺序找出来的，所以找到的是倒序的。(分析参考:Floyd最短路径算法)
Code1：
#include <bits/stdc++.h> using namespace std; const int maxn = 1005; int mp[maxn][maxn], pre[maxn][maxn]; int n, m; void init() { memset(mp, 0x3f, sizeof mp); for(int i = 1; i <= n; ++i) mp[i][i] = 0; for(int i = 1; i <= n; ++i) for(int j = 1; j <= n; ++j) pre[i][j] = i; } void Folyd() { for(int k = 1; k <= n; ++k) for(int i = 1; i <= n; ++i) for(int j = 1; j <= n; ++j) { if(mp[i][j] > mp[i][k]+mp[k][j]) { mp[i][j] = mp[i][k]+mp[k][j]; pre[i][j] = pre[k][j]; } } } void PrintPath(int start, int end) { int k = end; while(k != start) { printf("%d ", k); k = pre[start][k]; } printf("%d\n", k); } int main() { int u, v, w; cin >> n >> m; init(); for(int i = 1; i <= m; ++i) { cin >> u >> v >> w; mp[u][v] = mp[v][u] = w; } Folyd(); PrintPath(2, 3); return 0; } PrintPath: 3 4 5 2.
②
通过一个nex数组来记录路径，nex[i][j]表示从i到j的最短路径从i开始走的第一个点。这样整个最短路径中的nex[i][j]都是这个含义，则就表示出了最短路径，输出时是正序的。
Code2：
#include <bits/stdc++.h> using namespace std; const int maxn = 1005; int mp[maxn][maxn], nex[maxn][maxn]; int n, m; void init() { memset(mp, 0x3f, sizeof mp); for(int i = 1; i <= n; ++i) mp[i][i] = 0; for(int i = 1; i <= n; ++i) for(int j = 1; j <= n; ++j) nex[i][j] = j; } void Folyd() { for(int k = 1; k <= n; ++k) for(int i = 1; i <= n; ++i) for(int j = 1; j <= n; ++j) { if(mp[i][j] > mp[i][k]+mp[k][j]) { mp[i][j] = mp[i][k]+mp[k][j]; nex[i][j] = nex[i][k]; } } } void PrintPath(int start, int end) { int k = start; while(k != end) { printf("%d ", k); k = nex[k][end]; } printf("%d\n", k); } int main() { int u, v, w; cin >> n >> m; init(); for(int i = 1; i <= m; ++i) { cin >> u >> v >> w; mp[u][v] = mp[v][u] = w; } Folyd(); PrintPath(2, 3); return 0; }PrintPath: 2 5 4 3.
