Dijkstra算法示例程序
May 4, 2013
Graph
输入：一个有向图，顶点个数 n ,然后是每条边的起点，终点，权值。顶点序号从0开始，-1 -1 -1表示结束。 输出：顶点0到其他各顶点的最短路径长度，并输出对应的最短路径。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <algorithm>
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
using namespace std;
typedef long long int LL;
const int MAXN = 0x3f3f3f3f;
const int MIN = -0x3f3f3f3f;
const double eps = 1e-9;
const int dir[8][2] = {{0,1},{1,0},{0,-1},{-1,0},{-1,1},
{1,1},{1,-1},{-1,-1}};
const int MAX = 20;
int S[MAX], dist[MAX], path[MAX], edge[MAX][MAX];
int n;
void Dijkstra(int v0) {
int i, j, k;
for (i = 0; i < n; ++i) {
dist[i] = edge[v0][i]; S[i] = 0;
if (i != v0 && edge[v0][i] != MAXN) path[i] = v0;
else path[i] = -1;
}
S[v0] = 1; dist[v0] = 0;
for (i = 0; i < n-1; ++i) {
int Min = MAXN, u = v0;
for (j = 0; j < n;++j) {
if (S[j] == 0 && dist[j] < Min) {
Min = dist[j]; u = j;
}
}
S[u] = 1;
for (j = 0; j < n; ++j) {
if (S[j] == 0 && edge[u][j] != MAXN) {
int tmp = edge[u][j] + dist[u];
if (tmp < dist[j]) {
dist[j] = tmp; path[j] = u;
}
}
}
}
}
int main(void){
#ifndef ONLINE_JUDGE
freopen("dijkstra.in", "r", stdin);
#endif
scanf("%d",&n);
int u, v, w, i, j, k;
while (1) {
scanf("%d%d%d", &u, &v, &w);
if (u == -1 && v == -1 && w == -1) break;
edge[u][v] = w;
}
for (i = 0; i < n;++i) {
for (j = 0; j < n; ++j) {
if (i == j) edge[i][j] = 0;
else if (edge[i][j] == 0) edge[i][j] = MAXN;
}
}
Dijkstra(0);
for (i = 1; i < n;++i) {
printf("%d\t", dist[i]);
int Shortest[MAX]; k = 0;
Shortest[k] = i;
while (path[Shortest[k]] != 0) {
++k; Shortest[k] = path[Shortest[k-1]];
}
++k; Shortest[k] =0;
for (j = k; j > 0; --j) {
printf("%d->", Shortest[j]);
}
printf("%d\n", Shortest[0]);
}
return 0;
}
采用所谓的“倒向追踪”的方法记录最短路径的时候，要注意怎么存储路径。写的时候，这里出现了一个bug。 输出路径的时候，赶脚书上的写法有点儿挫……所以自己又写了一遍。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <algorithm>
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
using namespace std;
typedef long long int LL;
const int MAXN = 0x7fffffff;
const int MINN = -0x7fffffff;
const double eps = 1e-9;
const int dir[8][2] = {{0,1},{1,0},{0,-1},{-1,0},{-1,1},
{1,1},{1,-1},{-1,-1}};
const int MAX = 200;
int edge[MAX][MAX], dist[MAX], path[MAX]; bool S[MAX];
int n, m;
void Dijkstra(int u0) {
int i, j, k, u, Min;
for (i = 0; i < n; ++i) {
dist[i] = edge[u0][i]; S[i] = false;
if (u0!=i && edge[u0][i] != MAXN) path[i] = u0;
else path[i]= -1;
}
S[i] = true; dist[u0] = 0; path[u0] = -1;
for (i = 1; i < n; ++i) {
u = u0; Min = MAXN;
for (j = 0; j < n; ++j) {
if (S[j] == false && dist[j] < Min) {
Min = dist[j]; u = j;
}
}
S[u] = true;
for (j = 0; j < n; ++j) {
if (S[j] == false && edge[u][j] != MAXN) {
int tmp= edge[u][j] + dist[u];
if (tmp < dist[j]) {
dist[j] = tmp;
path[j] = u;
}
}
}
}
}
int main(void){
#ifndef ONLINE_JUDGE
freopen("dijkstra.in", "r", stdin);
#endif
int u, v, w;
memset(edge, 0, sizeof(edge));
scanf("%d", &n);
while (1) {
scanf("%d%d%d", &u, &v, &w);
if (u == -1 && v == -1 && w == -1) break;
edge[u][v] = w;
}
int i, j, k;
for (i = 0; i < n; ++i) {
for (j = 0; j < n; ++j) {
if (i == j) edge[i][j] = 0;
else if(edge[i][j] == 0) edge[i][j] = MAXN;
}
}
int Path[MAX]; Dijkstra(0);
for (i = 1; i < n; ++i) {
printf("%d\t",dist[i]);
k= 0; Path[0] = i; int ho = path[i];
while (ho != -1) {
Path[++k] = ho; ho = path[ho];
}
for (j = k; j > 0; --j) printf("%d->", Path[j]);
printf("%d\n", Path[0]);
}
return 0;
}
因为做了两道题目，都没有要求输出路径的，所以自己还是写一下输出路径的吧。注意一下，开始标记路径的时候，把和u0相连的标记为u0，其它的不相连的标记为-1.循环结束后，把path[u0]标记为-1，表示起点。Dijkstra算法最后求得的dist[]是u0到每个点的最短距离。 现在感觉，平时就要有意识地训练一下自己的查错能力，这样，真正比赛的时候，就不会因为找不出来错而着急了。