算法总结：图论———单源最短路
本文总结单源最短路算法，涵盖 Dijkstra 和 SPFA。
题目大意
给出一个有向图，请输出从某一点出发到所有点的最短路径长度。 输入三个整数 n, m, s，分别表示点的个数、有向边的个数、出发点的编号。 再输入 m 条边，每行包含三个整数 u, v, w，表示一条 u → v 的，长度为 w 的边。
存图
在求最短路前，要先处理输入的数据。 最好用的肯定是邻接表:
vector<pair<int, int>> g[N];
其中，g[i] 表示以第 i 个点（即输入中的 u）为起点的每条边（类型为 vector<pair<int,int>>），第一个参数为可以到达的点（即 v），第二个参数为 u → v 的边权 w。
输入方法如下：
scanf("%d%d%d", &n, &m, &s);
for (int i = 1; i <= m; i++) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
g[u].push_back({v, w});
}
另外，还可用链式前向星存图。
1. Dijkstra
先设 dis[i] 为从起点到达 i 号点的最短路长度。
核心思想
对于每一个已被松弛过的点，每次找到最小的 dis（假设为 s），遍历 s 能到达的每一个点并松弛它们。 （松弛：将某个点的最短路更新为一个原来更小的值）
示例
如上图，设起点为 1。 首先将 dis 数组全部改为 +∞，只将 dis[1] 改为 0。 ① 只有 1 是被松弛过的，所以松弛 1 周围的点（2 和 3），此时： dis[1] = 0, dis[2] = 5, dis[3] = 3, dis[4] = +∞, dis[5] = +∞。 ② 2 和 3 都已被松弛过，但 dis[3] 更小，所以先松弛 3 周围的点，此时： dis[1] = 0, dis[2] = 5, dis[3] = 3, dis[4] = 3+4 = 7, dis[5] = 3+4 = 7。 ③ 2,4,5 三个点中，dis[2] 最小，所以松弛 2 周围的点，此时： dis[1] = 0, dis[2] = 5, dis[3] = 3（因为 3<5+2，所以 dis[3] 仍为 3）, dis[4] = 5+1 = 6（因为 6<7，所以 dis[4] 变更为 6）, dis[5] = 7。 ④ 4,5 两点中，dis[4] 更小，所以松弛 4 周围的点，此时： dis[1] = 0, dis[2] = 5, dis[3] = 3, dis[4] = 6, dis[5] = 7（因为 7<6+2，所以 dis[5] 仍为 7）。 ⑤ 5 周围没有可以到达的点，松弛完毕。
证明
要用反证法。该算法对于边权非负的情况普遍正确。
代码实现及优化
先上代码（洛谷 P4779，保证每个点都能到达）：
#include <bits/stdc++.h>
std;
n, m, s;
dis[N];
vis[N];
vector<pair<, >> g[N];
{
(dis, , (dis));
dis[s] = ;
( i = ; i <= n; i++) {
u = , mn = ;
( j = ; j <= n; j++) {
(!vis[j] && dis[j] < mn) {
u = j;
mn = dis[j];
}
}
(u == ) ;
vis[u] = ;
( j = ; j < g[u].(); j++) {
v = g[u][j].first, w = g[u][j].second;
(mn + w < dis[v]) dis[v] = mn + g[u][j].second;
}
}
}
{
(, &n, &m, &s);
( i = ; i <= m; i++) {
u, v, w;
(, &u, &v, &w);
g[u].({v, w});
}
();
( i = ; i <= n; i++) (, dis[i]);
;
}
