C++ 图论实战：深入理解三种最短路径算法

在实际运行中，你会发现这个双重循环结构决定了它的时间复杂度较高。对于稠密图，使用邻接矩阵配合线性扫描找最小值是比较直观的写法；如果是稀疏图，通常会引入优先队列来优化查找 min 的过程。

Bellman-Ford 算法：处理负权与检测负环

当图中出现负权边时，Dijkstra 就失效了。Bellman-Ford 算法能解决这个问题，但代价是更高的时间复杂度。它的本质是暴力松弛：对图中的所有边重复进行松弛操作，最多进行 $n$ 轮（$n$ 为顶点数）。因为任何不含负环的最短路径最多只经过 $n-1$ 条边。

跑完 $n$ 轮后，再扫一遍所有边，如果还能更新距离，说明图中存在负权回路，此时最短路径不存在。

bool BellmanFord(const V& src, std::vector<W>& dist, std::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] = static_cast<int>(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;
}

这里有个小细节：我们在循环内部加了 if (!update) break;。这其实是一个常见的优化，因为在某些情况下，可能不需要跑满 $n$ 轮就能提前收敛，这样能节省一些不必要的计算。

Floyd-Warshall 算法：任意两点间的最短路径

如果你需要知道图中任意两个顶点之间的最短距离，而不是指定一个起点，Floyd-Warshall 算法是最直接的选择。它基于动态规划的思想，依次把每个点当作中转点，判断从 $i$ 到 $j$ 是直接走更近，还是经过中转点 $k$ 再走更近。

三层循环结束后，我们就得到了全图的最短路径矩阵。

void FloydWarshall(std::vector<std::vector<W>>& vvDist, std::vector<std::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] = static_cast<int>(i); // 前驱设为 i
            }
            if (i == j) {
                vvDist[i][j] = W(); // 自己到自己距离为 0
            }
        }
    }

    // 3. 动态规划更新：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) {
                // 如果经过 k 更近，则更新
                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];
                    // 更新前驱路径
                    vvpPath[i][j] = vvpPath[k][j];
                }
            }
        }
    }
}

关于路径还原，代码中 vvpPath[i][j] = vvpPath[k][j] 这一行很关键。它的意思是，如果 $i$ 到 $j$ 的最短路径经过了 $k$，那么 $j$ 的前驱就是 $k$ 到 $j$ 路径上的前驱。通过递归或迭代查询 pPath 数组，我们就能完整还原出路径序列。

这三种算法各有千秋：Dijkstra 快但不能抗负权，Bellman-Ford 能抗负权但慢，Floyd 适合全源但空间开销大。实际开发中，根据数据规模和约束条件选择合适的工具，往往比单纯追求算法复杂度更重要。