弗洛伊德算法c++
时间: 2024-06-22 19:00:45 浏览: 9
弗洛伊德(Floyd-Warshall)算法是一种用于求解图中最短路径的动态规划方法,它适用于带有权值的任意带权重的图(包括负权重)。在C++中,你可以使用邻接矩阵或邻接表来实现这个算法。
下面是C++中使用邻接矩阵实现弗洛伊德算法的一个基本步骤:
```cpp
#include <vector>
#include <limits>
// 定义一个矩阵表示图的边权
using Graph = std::vector<std::vector<int>>;
// 计算所有节点对之间的最短路径
void floydWarshall(const Graph& graph, int n) {
// 初始化距离矩阵,用INT_MAX表示无穷大
std::vector<std::vector<int>> dist(n, std::vector<int>(n, std::numeric_limits<int>::max()));
// 使用原图的边权填充初始距离矩阵
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
if (graph[i][j] != std::numeric_limits<int>::max())
dist[i][j] = graph[i][j];
// 对于所有中间节点k,更新所有节点对的距离
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] != std::numeric_limits<int>::max() &&
dist[k][j] != std::numeric_limits<int>::max())
dist[i][j] = std::min(dist[i][j], dist[i][k] + dist[k][j]);
// 最终得到的是所有节点对之间的最短路径
}
// 示例:
int main() {
Graph graph = {{0, 4, 0, 0, 0},
{4, 0, 8, 0, 0},
{0, 8, 0, 7, 0},
{0, 0, 7, 0, 9},
{0, 0, 0, 9, 0}};
int n = graph.size();
floydWarshall(graph, n);
// 输出最短路径
for (const auto& row : dist)
std::cout << row << "\n";
return 0;
}
```
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)