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

实际运行时，若使用优先队列优化，时间复杂度可降至 $O(E \log V)$，但在稠密图中简单的数组扫描往往更直观高效。

Bellman-Ford 算法：处理负权边与回路检测

当图中存在负权边时，Dijkstra 失效，此时应选用 Bellman-Ford 算法。它的本质是对所有边进行多次松弛，重复 $n$ 轮（$n$ 为顶点数）。因为任何不含负权环的最短路径最多经过 $n-1$ 条边。

该算法不仅能算出单源最短路径，还能在最后一轮松弛后检查是否还能更新距离。如果能更新，说明图中存在负权回路，最短路径不存在。

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] = 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 -> 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;
}

虽然逻辑简单，但 Bellman-Ford 的时间复杂度为 $O(V \cdot E)$，在处理大规模图时性能不如 SPFA 或 Dijkstra，但在需要检测负环的场景下它是首选。

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

Floyd-Warshall 算法用于求解任意两点之间的最短路径。它采用动态规划思想，依次将每个点作为中转点，判断从 $i$ 到 $j$ 是直接走更近，还是经过中转点 $k$ 再走更近。

三层循环跑完即可得到全图最短路径矩阵。代码结构紧凑，适合顶点数较少（通常 $V \le 500$）的场景。

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] = 0;
            }
        }
    }

    // 最短路径的更新：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 作为中间点尝试去更新 i->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；否则继承 k->j 的前驱
                    vvpPath[i][j] = vvpPath[k][j];
                }
            }
        }
    }
}

总结来说，选择算法时要看场景：无负权求单源用 Dijkstra，有负权求单源用 Bellman-Ford，求全源且点数不多用 Floyd。理解它们的底层逻辑，比死记硬背代码更重要。