无权图 单源最短路 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数组记录某顶点到源点当前最短路径长。
- 执行V - 1轮操作，每轮都遍历图中所有边。
松弛操作：对每条边u-->v, 若以u为中介，能使dist[v]更小，则更新。 - 若图中没有从源点可达的负环，那么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;
}
