请用邻接表的存储结构写一个Floyd算法
时间: 2024-03-03 16:51:03 浏览: 5
好的,以下是基于邻接表存储结构的Floyd算法实现:
```
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 100;
const int INF = 0x3f3f3f3f;
int n, m;
int dist[maxn][maxn]; // 存储两点之间的距离,若不连通则为INF
struct Edge {
int to, w;
int next;
} edges[maxn * maxn]; // 存储边的信息
int head[maxn], cnt; // 邻接表存储结构
void addEdge(int u, int v, int w) {
edges[++cnt].to = v;
edges[cnt].w = w;
edges[cnt].next = head[u];
head[u] = cnt;
}
void init() {
memset(head, -1, sizeof(head));
memset(dist, INF, sizeof(dist));
cnt = -1;
}
void floyd() {
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
}
int main() {
cin >> n >> m;
init();
int u, v, w;
for (int i = 1; i <= m; i++) {
cin >> u >> v >> w;
addEdge(u, v, w);
dist[u][v] = w;
}
floyd();
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (dist[i][j] == INF) {
cout << "INF ";
} else {
cout << dist[i][j] << " ";
}
}
cout << endl;
}
return 0;
}
```
在这个实现中,我们使用了邻接表存储图的信息,然后在输入边的同时,将边的信息存储到邻接表中,并且将两点之间的距离存储到dist数组中。然后,我们使用Floyd算法不断更新dist数组,最终得到任意两点之间的最短距离。最后,我们遍历dist数组,输出最短距离即可。