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

最短路径问题是图论中的核心议题，旨在从带权有向图中找到两点间权值总和最小的路径。在实际工程中，根据图的特性（如是否存在负权边）和计算需求（单源或全源），我们需要选择合适的算法。

Dijkstra 算法：非负权图的贪心策略

Dijkstra 是解决单源最短路径的经典算法，采用贪心思想。它仅适用于没有负权边的图。算法维护一个已确定最短路径的集合，每次从未确定的节点中选出距离起点最近的点，用它去松弛邻接点的距离估计值，直到所有节点都被处理。

Dijkstra 算法执行过程示意图

实现时需要注意初始化距离数组为无穷大，并将起点的距离设为 0。松弛操作是核心：如果 dist[u] + weight(u, v) < dist[v]，则更新 v 的距离和前驱节点。

// src 是选定的起点，dist 记录起点到各点的最短路径，pPath 记录前驱顶点下标
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. 在未确定集合中选距离最小且未访问的节点 u
        int u = 0;
        W min_dist = MAX_W;
        for (size_t i = 0; i < n; ++i) {
            if (!S[i] && dist[i] < min_dist) {
                u = i;
                min_dist = dist[i];
            }
        }
        
        S[u] = true;

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

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

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

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

Bellman-Ford 算法松弛过程

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

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。理解它们的底层逻辑，比死记硬背代码更重要。