图◆最短路 |BFS、 Dijkstra、Floyd、Bellm

无权图 单源最短路 BFS

带权图 单源最短路 Dijkstra O（V*logV + E）

任意两个顶点间的最短路 Floyd O（N^3）

可以有负权边，不可有负权环

含负权图的单源最短路 Bellman-Ford O(V*E)

优化的Bellman-Ford：SPFA O(kE)

每遍处理只对特定顶点出发的边做松弛操作。可以将发生变化的顶点的记录下来，在下一遍处理时对一这些顶点为源点的边做松弛操作。

BFS、Dijkstra见暴力搜索 | BFS、树、图 | DFS & BFS、图◆单源最短路径 | Dijkstra。

Floyd

O（N^3）

问题

全源最短路

策略

3层循环，暴力枚举以某顶点v为中介时，顶点u和顶点w的距离，若比原先小，则更新。

最短路径保存

path[][]，初始化为-1。
若更新 dist[u][v] 为 dist[u][i] + dist[i][v]，相应更新path[u][v]为i。

图源

实现

#include <cstdio>
#include <algorithm>

#define MAXN 21
#define INF 0x3fffffff
using namespace std;
int n_vertex, m_edge, dist[MAXN][MAXN];

void Floyd() {
    for (int i = 1; i <= n_vertex; ++i) {
        for (int j = 1; j <= n_vertex; ++j) {
            for (int k = 1; k <= n_vertex; ++k) {
                if (dist[j][i] != INF && dist[i][k] != INF && dist[j][i] + dist[i][k] < dist[j][k])
                    dist[j][k] = dist[k][j] = dist[j][i] + dist[i][k];
            }
        }
    }
}

// premise: 连通图
int main() {
    scanf("%d%d", &n_vertex, &m_edge);
    int v1, v2, weight;
    fill(dist[0], dist[0] + MAXN * MAXN, INF);
    for (int i = 0; i < m_edge; ++i) {
        scanf("%d%d%d", &v1, &v2, &weight);
        dist[v1][v2] = dist[v2][v1] = weight;
    }
    Floyd();
    int xx, yy;
    scanf("%d%d", &xx, &yy);
    (dist[xx][yy] == INF) ? printf("No path") : printf("%d", dist[xx][yy]);
    return 0;
}

Bellman-Ford

O(VE)

问题：含负权的单源最短路

Dijkstra不能用来处理含负权边的图的最短路问题。因为若图中存在负环，且从源点可达该环，那么在这个环上绕圈可以获得更短的路径（负无穷）……若不存在负环，则最短路径的求解不受影响。

策略

dist数组记录某顶点到源点当前最短路径长。

1. 执行V - 1轮操作，每轮都遍历图中所有边。
   松弛操作：对每条边u-->v, 若以u为中介，能使dist[v]更小，则更新。
2. 若图中没有从源点可达的负环，那么dist数组所有值都已经最优。
   再执行一轮，若仍可被松弛，说明图中存在从源点可达的负环。

证明

来自「算法笔记」

实现

需要遍历所有边，邻接表实现起来方便。若采用邻接矩阵，复杂度将增大到O(V^3)。
以1003 Emergency (25 分)为例。

• ⚠️注意路径条数的初始化、更新：源点路径数量初始化为 1。

  
  来自「算法笔记」

#include <cstdio>
#include <algorithm>
#include <vector>
#include <set>

#define MAXN 501
#define INF 0x3fffffff
using namespace std;
// dist 最短路长度   v_weight_sum 最短路点权和   cnts 最短路条数
int nn, mm, src, target, teams[MAXN], dist[MAXN], v_weight_sum[MAXN] = {0}, cnts[MAXN] = {0};
vector<pair<int, int>> graph[MAXN];
set<int> pre[MAXN];

bool BF(int start) {
    fill(dist, dist + MAXN, INF);
    dist[start] = 0;
    v_weight_sum[start] = teams[start];
    cnts[start] = 1;  // 注意！！！
    for (int i = 1; i < nn; ++i) { // loop n-1
        bool _relax = false;
        for (int j = 0; j < nn; ++j) {
            for (auto item:graph[j]) {
                if (dist[j] + item.second < dist[item.first]) {
                    dist[item.first] = dist[j] + item.second;
                    v_weight_sum[item.first] = v_weight_sum[j] + teams[item.first];
                    pre[item.first].clear();
                    pre[item.first].insert(j);
                    cnts[item.first] = cnts[j];
                    _relax = true;
                } else if (dist[j] + item.second == dist[item.first]) {
                    pre[item.first].insert(j);
                    // 注意！！！ cnts[item.first] += cnts[j];
                    cnts[item.first] = 0;
                    for (auto item1:pre[item.first]) {
                        cnts[item.first] += cnts[item1];
                    }
                    if (v_weight_sum[j] + teams[item.first] > v_weight_sum[item.first]) {
                        v_weight_sum[item.first] = v_weight_sum[j] + teams[item.first];
                    }
                    _relax = true;
                }
            }
        }
        if (!_relax) break;
    }
    for (int i = 0; i < nn; ++i) { //判是否存在负环 此题没必要 = =
        for (auto item:graph[i]) {
            if (dist[i] + item.second < dist[item.first])
                return false;
        }
    }
    return true;
}

int main() {
    scanf("%d%d%d%d", &nn, &mm, &src, &target);
    for (int i = 0; i < nn; ++i) {
        scanf("%d", &teams[i]);
    }
    int v1, v2, weight;
    for (int i = 0; i < mm; ++i) {
        scanf("%d%d%d", &v1, &v2, &weight);
        graph[v1].emplace_back(v2, weight);
        graph[v2].emplace_back(v1, weight);
    }
    BF(src);
    printf("%d %d\n", cnts[target], v_weight_sum[target]);
    return 0;
}