Floyd 算法c++
时间: 2023-08-19 10:06:32 浏览: 52
Floyd 算法(Floyd-Warshall 算法)是一种用于求解图中所有节点对最短路径的算法。下面是用 C++ 实现 Floyd 算法的示例代码:
```cpp
#include <iostream>
#include <climits>
#define INF INT_MAX
void floydWarshall(int graph[][4], int V) {
int dist[V][V];
// 初始化距离矩阵
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
dist[i][j] = graph[i][j];
}
}
// 通过中间节点 k 逐步更新最短路径
for (int k = 0; k < V; k++) {
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
// 如果经过节点 k 的路径比直接路径更短,则更新距离
if (dist[i][k] != INF && dist[k][j] != INF && dist[i][k] + dist[k][j] < dist[i][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}
// 打印最短路径矩阵
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
if (dist[i][j] == INF) {
std::cout << "INF ";
} else {
std::cout << dist[i][j] << " ";
}
}
std::cout << std::endl;
}
}
int main() {
int graph[4][4] = {{0, 5, INF, 10},
{INF, 0, 3, INF},
{INF, INF, 0, 1},
{INF, INF, INF, 0}};
floydWarshall(graph, 4);
return 0;
}
```
这是一个简单的实现示例,通过传入一个邻接矩阵来计算所有节点对的最短路径。在这个示例中,图中共有4个节点,用一个4x4的邻接矩阵表示。其中,INF 表示两个节点之间没有直接连接。程序输出的结果是一个4x4的矩阵,表示任意两个节点之间的最短路径长度。