C++ 图论实战：Dijkstra、Bellman-Ford 与 Floyd 最短路径算法详解 | 极客日志

C++算法

C++ 图论实战：Dijkstra、Bellman-Ford 与 Floyd 最短路径算法详解

C++ 图论中最短路径的三种核心算法解析。涵盖 Dijkstra 贪心策略处理非负权图，Bellman-Ford 应对含负权边的场景及环路检测，以及 Floyd 动态规划解决全源最短路径问题。通过代码实现展示松弛操作与路径记录机制，帮助开发者理解不同算法的时间复杂度差异与适用边界。

追风少年发布于 2026/3/27更新于 2026/4/241 浏览

C++ 图论实战：Dijkstra、Bellman-Ford 与 Floyd 最短路径算法详解

最短路径问题旨在从带权有向图中找到从一个顶点到另一个顶点的路径，使得路径上各边的权值总和最小。在实际工程中，这通常涉及网络路由、地图导航等场景。

Dijkstra 算法

Dijkstra 是单源最短路径的经典贪心算法，适用于没有负权边的图。它的核心思想是从起点出发，每次选择当前距离最小且未确定最短路径的节点，用它去松弛（更新）所有邻接点的最短路径估计值，标记该节点为'已确定'，重复此过程直到所有节点处理完毕。

图结构示例

下面是一个基于邻接矩阵实现的 Dijkstra 函数。注意这里假设存在一个 Graph 类，包含 _matrix 和 _vertexs 成员变量。

void Dijkstra(const V& src, vector<W>& dist, vector<int>& pPath) {
    size_t srci = GetVertexIndex(src);
    size_t n = _vertexs.size();
    
    // 初始化距离数组和前驱节点数组
    dist.resize(n, MAX_W);
    pPath.resize(n, -1);
    dist[srci] = 0;
    pPath[srci] = srci; // 起点的前驱指向自己

    // S 集合记录已确定最短路径的顶点
    vector<bool> S(n, false);

    for (size_t j = 0; j < n; ++j) {
        // 1. 选最短路径顶点且不在 S 中
        int u = 0;
        W minDist = MAX_W;
        for (size_t i = 0; i < n; ++i) {
            if (!S[i] && dist[i] < minDist) {
                u = i;
                minDist = dist[i];
            }
        }

        S[u] = true;

        // 2. 松弛更新 u 连接顶点 v
        
         ( v = ; v < n; ++v) {
             (!S[v] && _matrix[u][v] != MAX_W && dist[u] + _matrix[u][v] < dist[v]) {
                dist[v] = dist[u] + _matrix[u][v];
                pPath[v] = u;
            }
        }
    }
}

bool BellmanFord(const V& src, vector<W>& dist, vector<int>& pPath) {
    size_t n = _vertexs.size();
    size_t srci = GetVertexIndex(src);

    // 初始化
    dist.resize(n, MAX_W);
    pPath.resize(n, -1);
    dist[srci] = W(); // 起点距离为 0

    // 总体最多更新 n 轮
    for (size_t k = 0; k < n; ++k) {
        bool update = false;
        // cout << "更新第:" << k << "轮" << endl; // 调试时可开启
        
        for (size_t i = 0; i < n; ++i) {
            for (size_t j = 0; j < n; ++j) {
                // 尝试松弛 srci -> i + i -> j
                if (_matrix[i][j] != MAX_W && dist[i] != MAX_W && dist[i] + _matrix[i][j] < dist[j]) {
                    update = true;
                    dist[j] = dist[i] + _matrix[i][j];
                    pPath[j] = i;
                }
            }
        }
        // 优化：如果这一轮没有更新，说明已经收敛，提前结束
        if (!update) break;
    }

    // 检测负权回路
    for (size_t i = 0; i < n; ++i) {
        for (size_t j = 0; j < n; ++j) {
            if (_matrix[i][j] != MAX_W && dist[i] + _matrix[i][j] < dist[j]) {
                return false; // 存在负权回路
            }
        }
    }
    return true;
}

void FloydWarshall(vector<vector<W>>& vvDist, vector<vector<int>>& vvpPath) {
    size_t n = _vertexs.size();
    vvDist.resize(n);
    vvpPath.resize(n);

    // 1. 初始化权值和路径矩阵
    for (size_t i = 0; i < n; ++i) {
        vvDist[i].resize(n, MAX_W);
        vvpPath[i].resize(n, -1);
    }

    // 2. 直接相连的边更新一下
    for (size_t i = 0; i < n; ++i) {
        for (size_t j = 0; j < n; ++j) {
            if (_matrix[i][j] != MAX_W) {
                vvDist[i][j] = _matrix[i][j];
                vvpPath[i][j] = i;
            }
            if (i == j) {
                vvDist[i][j] = W(); // 自身距离为 0
            }
        }
    }

    // 3. 最短路径的更新：i -> {其他顶点} -> j
    // k 作为中间点尝试去更新 i->j 的路径
    for (size_t k = 0; k < n; ++k) {
        for (size_t i = 0; i < n; ++i) {
            for (size_t j = 0; j < n; ++j) {
                if (vvDist[i][k] != MAX_W && vvDist[k][j] != MAX_W && 
                    vvDist[i][k] + vvDist[k][j] < vvDist[i][j]) {
                    vvDist[i][j] = vvDist[i][k] + vvDist[k][j];
                    // 路径记录：如果 k->j 直接相连，上一个点就是 k；
                    // 否则 vvpPath[k][j] 存的就是 x (k->...->x->j)
                    vvpPath[i][j] = vvpPath[k][j];
                }
            }
        }
    }
}