C++ 图论最短路径算法：Dijkstra、Bellman-Ford 与 Floyd

二、Bellman_Ford 算法

Bellman-Ford 算法能用来解决负权图的单源最短路径问题，但是它的时间复杂度高于 Dijkstra 算法，本质是暴力求解。从起点出发，把图里所有边从头到尾松弛一遍，重复 n 次，就能算出起点到所有点的最短路径；因为任何最短路径最多只经过 n-1 条边。跑完之后再扫一遍所有边，如果还能更新距离，就说明图里有负权回路，最短路径不存在。

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) {
        // i->j 更新松弛
        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 == false) {
            break;
        }
    }
    // 还能更新就是带负权回路
    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] + _matrix[i][j] < dist[j]) {
                return false;
            }
        }
    }
    return true;
}

三、Floyd_Warshall 算法

Floyd-Warshall 算法是求任意两点之间最短路径的算法，依次把每个点当作中转点，判断从 i 到 j 是直接走更近，还是经过这个中转点 k 再走更近，不断更新所有点对的最短距离，三层循环跑完就得到全图最短路径。

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