C++ 图论实战：三种经典最短路径算法详解

二、Bellman-Ford 算法

当图中出现负权边时，Dijkstra 就无能为力了，这时候得用 Bellman-Ford 算法。它本质上是暴力求解，通过不断松弛边来逼近最优解。因为任何简单路径最多只经过 n-1 条边，所以只需要把图里所有边从头到尾松弛一遍，重复 n 次即可。

跑完之后再扫一遍所有边，如果还能更新距离，说明图中存在负权回路，此时最短路径不存在。虽然时间复杂度比 Dijkstra 高，但在处理负权图时它是可靠的选择。

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) {
                // 如果 i->j 有边，且经过 i 能缩短 srci->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;
}

三、Floyd-Warshall 算法

如果你需要计算图中任意两点之间的最短路径，而不是单源，那 Floyd-Warshall 是最直接的选择。它采用动态规划思想，依次把每个点当作中转点，判断从 i 到 j 是直接走更近，还是经过这个中转点 k 再走更近。

三层循环跑完就能得到全图最短路径矩阵。代码实现上要注意初始化对角线为 0，非连通边设为无穷大。虽然时间复杂度是 O(n³)，但对于节点数不多（比如几百个以内）的全源最短路问题，它非常实用且代码简洁。

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

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

    // 直接相连的边更新一下
    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
            }
        }
    }

    // 最短路径的更新：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];
                    // 找跟 j 相连的上一个邻接顶点
                    // 如果 k->j 直接相连，上一个点就是 k；否则递归查找
                    vvpPath[i][j] = vvpPath[k][j];
                }
            }
        }
    }
}