题意:给n个节点m条边,给出每条边相连节点,与边的权值,求1到n的最短路
Dijkstra算法:
#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int n, m, g[105][105], path[105], vis[105];
int main()
{
while (cin >> n >> m && n && m) {
memset(g, 0x3f3f3f3f, sizeof(g));
memset(vis, 0, sizeof(vis));
memset(path, 0x3f3f3f3f, sizeof(path));
for (int i = 0; i < m; i++) {
int x, y, dis;
cin >> x >> y >> dis;
g[x][y] = min(dis, g[x][y]);
g[y][x] = g[x][y];
}
for (int i = 1; i <= n; i++) {
path[i] = g[1][i];
}
while (true) {
int k = -1;
for (int i = 1; i <= n; i++)
if (!vis[i] && (k == -1 || path[i] < path[k]))
k = i;
if (k == -1)
break;
vis[k] = 1;
for (int i = 1; i <= n; i++)
if (!vis[i] && path[k] + g[k][i] < path[i]) {
path[i] = path[k] + g[k][i];
}
}
cout << path[n] << endl;
}
}
Floyd算法:
#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
long long n, m, g[105][105];
int main()
{
while (cin >> n >> m && n && m) {
memset(g, 0x3f3f3f3f, sizeof(g));
for (int i = 0; i < m; i++) {
long long x, y, dis;
cin >> x >> y >> dis;
g[x][y] = min(g[x][y], dis);
g[y][x] = g[x][y];
}
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (g[i][j] > g[i][k] + g[k][j]) {
g[i][j] = g[i][k] + g[k][j];
}
cout << g[1][n] << endl;
}
}