考研数据结构Floyd算法
时间: 2023-12-23 21:27:48 浏览: 105
Floyd算法是一种用于解决图中最短路径问题的算法。它可以计算出图中任意两个顶点之间的最短路径长度。下面是Floyd算法的C++代码示例:
```cpp
#include <iostream>
using namespace std;
#define INF 99999
void floyd(int graph[][4], int n) {
int dist[n][n];
// 初始化距离矩阵
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
dist[i][j] = graph[i][j];
}
}
// 计算最短路径
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (dist[i][k] + dist[k][j] < dist[i][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}
// 输出最短路径矩阵
cout << "最短路径矩阵:" << endl;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (dist[i][j] == INF) {
cout << "INF ";
} else {
cout << dist[i][j] << " ";
}
}
cout << endl;
}
}
int main() {
int graph[4][4] = {
{0, 5, INF, 10},
{INF, 0, 3, INF},
{INF, INF, 0, 1},
{INF, INF, INF, 0}
};
int n = 4;
floyd(graph, n);
return 0;
}
```
该代码中,我们首先定义了一个图的邻接矩阵表示,其中INF表示两个顶点之间没有直接连接。然后,我们使用Floyd算法计算出任意两个顶点之间的最短路径长度,并将结果存储在距离矩阵dist中。最后,我们输出距离矩阵,其中INF表示两个顶点之间没有路径。
阅读全文