c++中如何实现Floyd算法_c++ Floyd算法实现方法-C++-PHP中文网

c++中如何实现Floyd算法_c++ Floyd算法实现方法

尼克

发布： 2025-10-01 19:44:02

原创

934人浏览过

Floyd算法通过动态规划求解所有顶点对间最短路径，核心是三重循环松弛操作，时间复杂度O(n³)，适用于小规模图且可处理负权边。

c++中如何实现floyd算法_c++ floyd算法实现方法

在C++中实现Floyd算法（也称Floyd-Warshall算法）用于求解图中所有顶点对之间的最短路径。该算法适用于带权有向图或无向图，能处理负权边（但不能有负权环）。核心思想是动态规划，通过中间节点逐步更新最短路径。

算法基本原理

Floyd算法基于这样一个事实：如果从顶点i到j的最短路径经过某个中间顶点k，那么这条路径可以拆分为i到k和k到j的两段最短路径。通过枚举所有可能的中间点k，不断松弛任意两点间的距离。

设dist[i][j]表示从顶点i到j的当前最短距离，初始时为图的邻接矩阵。算法进行如下更新：

dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

立即学习“C++免费学习笔记（深入）”；

法语写作助手

法语助手旗下的AI智能写作平台，支持语法、拼写自动纠错，一键改写、润色你的法语作文。

查看详情

实现步骤

以下是具体的实现流程：

初始化一个二维数组dist，大小为n×n（n为顶点数），表示任意两点间的距离
若i==j，则dist[i][j]为0；若i与j之间有边，则赋值为对应权重；否则设为一个极大值（如INT_MAX/2）
三重循环：外层枚举中间点k，内层枚举起点i和终点j，尝试通过k更新i到j的距离
最终dist[i][j]即为i到j的最短路径长度

C++代码示例

下面是一个完整的C++实现：

#include <iostream>
#include <climits>
#include <vector>
using namespace std;

const int INF = INT_MAX / 2; // 防止加法溢出

void floyd(vector<vector<int>>& dist) {
    int n = dist.size();

    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] != INF && dist[k][j] != INF) {
                    dist[i][j] = min(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 n = 4;
    vector<vector<int>> graph = {
        {0,   3,   INF, 7},
        {8,   0,   2,   INF},
        {5,   INF, 0,   1},
        {2,   INF, INF, 0}
    };

    floyd(graph);
    return 0;
}

登录后复制