C++ 图论解析：最短路径算法详解 | 极客日志

C++算法

C++ 图论解析：最短路径算法详解

图论最短路径问题主要涉及三种经典算法。Dijkstra 算法基于贪心策略解决非负权单源最短路径；Bellman-Ford 算法通过松弛操作处理含负权边的情况并检测负环；Floyd-Warshall 算法利用动态规划计算任意两点间的最短距离。开发者应根据图的权重特征及查询需求选择合适的算法实现。

莫名其妙发布于 2026/3/21更新于 2026/5/75 浏览

C++ 图论解析：最短路径算法详解

一、Dijkstra 算法

最短路径问题是指，在带权的有向图中从某一顶点出发，找到通往另一顶点的最短路径，'最短'指的是沿路径各边的权值总和最小。

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

Dijkstra 算法示意图

// 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; // 已经确定最短路径的顶点集合

    vector<bool> S(n, false);
    for (size_t j = 0; j < n; ++j) {
        // 选最短路径顶点且不在 S 中，更新其他路径
        int u = 0;
        W min = MAX_W;
        for (size_t i = 0; i < n; ++i) {
            if (!S[i] && dist[i] < min) {
                u = i;
                min = dist[i];
            }
        }
        S[u] = true;

        // 松弛更新 u 连接顶点 v: srci->u + u->v < srci->v 时更新
        for (size_t 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);

    // vector<W> dist, 记录 srci-其他顶点最短路径权值数组
    dist.resize(n, MAX_W);
    // vector<int> pPath 记录 srci-其他顶点父顶点数组
    pPath.resize(n, -1);

    // 先更新 srci->srci 为缺省值
    dist[srci] = W();

    // 总体最多更新 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;
                    //cout << _vertexs[i] << "->" << _vertexs[j] << ":" << _matrix[i][j] << endl;
                    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);

    // 初始化权值和路径矩阵
    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();
            }
        }
    }

    // 最短路径的更新 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];
                    // 找跟 j 相连的上一个邻接顶点
                    // 如果 k->j 直接相连，上一个点就 k，vvpPath[k][j] 存就是 k
                    // 如果 k->j 没有直接相连，k->...->x->j，vvpPath[k][j] 存就是 x
                    vvpPath[i][j] = vvpPath[k][j];
                }
            }
        }
    }
}