1.Dijkstra算法：解决无负权边的带权有向图或无向图的单源最短路问题
#include<stdio.h>#include<string.h># define N 110# define INF 0xfffffff# define Min(a, b) (a < b ? a : b)int G[N][N];int dist[N];int vis[N];int n, m;void Start(){ int i, j; memset(vis, 0, sizeof(vis)); for (i = 1; i <= n; i++) { dist[i] = INF; for (j = 1; j <= n; j++) G[i][j] = INF; }}void Dij(){ int i, j, idex, M; dist[1] = 0; for (i = 1; i <= n; i++) { M = INF; for (j = 1; j <= n; j++) { if (vis[j] == 0 && dist[j] < M) { M = dist[j]; idex = j; } } vis[idex] = 1; //每次找到最小的就置为1 for (j = 1; j <= n; j++) { if (vis[j] == 0 && (dist[j] > dist[idex] + G[idex][j])) { dist[j] = dist[idex] + G[idex][j]; //将每个首位到 j 的最短距离记录下来 } } }}int main (){ int i, a, b, c; while (scanf("%d %d", &n, &m), n+m) { Start(); for (i = 0; i < m; i++) { scanf("%d %d %d", &a, &b, &c); G[a][b] = Min(G[a][b], c); G[b][a] = G[a][b]; } Dij(); printf("%d\n", dist[n]); } return 0;}
2. Floyd算法：每一对顶点之间的最短路径
#include<stdio.h>#include<string.h># define N 110# define INF 0xfffffff# define Min(a, b) (a < b ? a : b)int G[N][N];int n, m;void Start(){ int i, j; for (i = 1; i <= n; i++) { for (j = 1; j <= n; j++) G[i][j] = INF; }}void Dij(){ int i, j, k; for (k = 1; k <= n; k++) { for (i = 1; i <= n; i++) { for (j = 1; j <= n; j++) { G[i][j] = Min(G[i][k]+G[k][j], G[i][j]); } } }}int main (){ int i, a, b, c; while (scanf("%d %d", &n, &m), n+m) { Start(); for (i = 0; i < m; i++) { scanf("%d %d %d", &a, &b, &c); G[a][b] = Min(G[a][b], c); G[b][a] = G[a][b]; } Dij(); printf("%d\n", G[1][n]); } return 0;}
3.Dijkstra算法的延伸：(邻接矩阵)
#include#include #include #define maxn 1100#define INF 0xfffffffusing namespace std;struct node{ int e, w;};vector G[maxn];int visit[maxn], dist[maxn], n;void Init(){ int i; memset(visit, 0, sizeof(visit)); for (i = 0; i <= n; i++) { dist[i] = INF; G[i].clear(); }}int Dist(){ dist[1] = 0; node no; int i, j, idex, Min, len; for (i = 1; i <= n; i++) { Min = INF; for (j = 1; j <= n; j++) { if (visit[j] == 0 && dist[j] < Min) { idex = j; Min = dist[j]; } } visit[idex] = 1; len = G[idex].size(); for (j = 0; j < len; j++) { no = G[idex][j]; if (visit[no.e] == 0 && dist[no.e] > dist[idex] + no.w) dist[no.e] = dist[idex] + no.w; } } return dist[n];}int main (){ int m, i, ans, a, b, c; while (scanf("%d %d", &n, &m), n+m) { Init(); node no; for (i = 1; i <= m; i++) { scanf("%d %d %d", &a, &b, &c); no.e = b; no.w = c; G[a].push_back(no); no.e = a; G[b].push_back(no); } ans = Dist(); printf("%d\n", ans); } return 0;}/*vector a;a.push_back(i);a.size();G[i].clear();*/
4.spfa算法：
#include#include #include #include #define maxn 110#define INF 0xfffffffusing namespace std;int G[maxn][maxn], visit[maxn], dist[maxn], n;void Init(){ int i, j; for (i = 0; i <= n; i++) { visit[i] = 0; dist[i] = INF; for (j = 0; j <= n; j++) G[i][j] = INF; }}int Dist(){ dist[1] = 0; queue Q; int i, start; start = 1; Q.push(start); while (!Q.empty()) { start = Q.front(); Q.pop(); for (i = 1; i <= n; i++) { if (dist[i] > dist[start] + G[start][i]) { dist[i] = dist[start] + G[start][i]; if (visit[i] == 0) { Q.push(i); visit[i] = 1; } } } visit[start] = 0; } return dist[n];}int main (){ int m, i, a, b, c, ans; while (scanf("%d %d", &n, &m), n+m) { Init(); for (i = 1; i <= m; i++) { scanf("%d %d %d", &a, &b, &c); G[a][b] = min(G[a][b], c); G[b][a] = G[a][b]; } ans = Dist(); printf("%d\n", ans); } return 0;}
5.spfa算法：（延伸）
#include#include #define INF 0xfffffff#define N 110#define M 100010using namespace std;int n, visit[N], dist[N], road[M];struct node{ int s, e, t, next;}no[M];void Init(){ int i; for (i = 1; i <= n; i++) { dist[i] = INF; visit[i] = 0; road[i] = -1; }}void Add(int s, int e, int t, int k){ no[k].s = s; no[k].e = e; no[k].t = t; no[k].next = road[s]; road[s] = k;}void Dist(){ queue Q; int x, i, y; x = 1; Q.push(x); dist[1] = 0; visit[1] = 1; while (!Q.empty()) { x = Q.front(); Q.pop(); for (i = road[x]; i != -1; i = no[i].next) { y = no[i].e; if (dist[y] > dist[x] + no[i].t) { dist[y] = dist[x] + no[i].t; if (visit[y] == 0) { Q.push(y); visit[y] = 1; } } } visit[x] = 0; }}int main (){ int m, s, e, t, k; while (scanf("%d %d", &n, &m), n+m) { k = 1; Init(); while (m--) { scanf("%d %d %d", &s, &e, &t); Add(s, e, t, k++); Add(e, s, t, k++); } Dist(); printf("%d\n", dist[n]); } return 0;}