最短路径算法

SPFA

SPFA 算法是基于Bellman-ford\text{Bellman-ford} 方程,具体算法描述如下
for i=1 to G.V1\textbf{for} \ i = 1 \ \textbf{to} \ |G.V|-1
for each edge(u,v)G.E:Relax(u,v,w)\quad \textbf{for} \ \text{each edge}(u, v) \in G.E: \quad \text{Relax}(u, v, w)
for each edge(u,v)G.E\textbf{for} \text{ each edge}(u, v) \in G.E
if v.d>u.d+w(u,v):return FALSE\quad \textbf{if} \ v.d > u.d + w(u, v): \quad \text{return FALSE}
return TRUE\text{return TRUE}

证明,定义最短路径权重 路径p=[v0,v1,,vk]p = [v_0, v_1, \cdots, v_k]w(p)=i=1kw(vi1,vi)w(p) = \displaystyle \sum_{i=1}^{k} w(v_{i-1}, v_i)

δ(u,v)={min{w(p):upv}如果存在一条从 u 到 v 的路径+\delta(u, v) = \begin{cases} \min \{w(p): u \xrightarrow{p} v \} && \text{如果存在一条从 u 到 v 的路径} \\ +\infty \end{cases}

结论bellman-ford\text{bellman-ford} 算法返回TRUE\text{TRUE} 当且仅当图GG 中不包含负权重的环路

对于(u,v)E,δ(s,v)δ(s,u)+w(u,v),s(u, v) \in E, \quad \delta(s, v) \leqslant \delta(s, u) + w(u, v), s 为源点

  • bellman-ford\text{bellman-ford} 算法如果能正确终止,对于(u,v)E\forall (u, v) \in E,我们有

    v.d=δ(s,v)δ(s,u)+w(u,v)=u.d+w(u,v)v.d = \delta(s, v) \leqslant \delta(s, u) + w(u, v) = u.d + w(u, v)

  • 现在假定图GG 包含一个权重为负的环路,并且该环路可以从源点ss 到达,不妨设环路为
    c=v0,v1,,vkc=\langle v_0, v_1, \cdots , v_k \rangle,其中v0=vkv_0 = v_k,那么

    i=1kw(vi1,vi)<0\sum_{i=1}^{k} w(v_{i-1}, v_i) < 0

    假设环路存在的情况下,bellman-ford\text{bellman-ford} 返回的是TRUE\text{TRUE},那么此时vi.dvi1.d+w(vi1,vi)v_{i}.d \leqslant v_{i-1}.d + w(v_{i-1}, v_i)
    i=1,2,,ki = 1, 2, \cdots , k,将环路上的不等式求和,我们有

    i=1kvi.dk=1k(vi1.d+w(vi1,vi))=i=1kvi1.d+i=1kw(vi1,vi)\sum_{i=1}^{k} v_i.d \leqslant \sum_{k=1}^{k} (v_{i-1}.d + w(v_{i-1}, v_i)) = \sum_{i=1}^{k} v_{i-1}.d + \sum_{i=1}^{k} w(v_{i-1}, v_i)

    注意到v0=vkv_0 = v_k,所以有

    i=1kvi.d=i=1kvi1.d\sum_{i=1}^{k} v_i.d = \sum_{i=1}^{k} v_{i-1}.d

    从而0k=1kw(vi1,vi)0 \leqslant \displaystyle \sum_{k=1}^{k}w(v_{i-1}, v_i),导出矛盾

SPFA算法实现,思想是一个点可能出队,入队多次
需要用一个inq[]\textbf{inq}[\cdots] 数组判断点是否在队列中
如果判定负环的话,还需要一个cnt\text{cnt} 数组,cnt(x)\text{cnt}(x) 表示从δ(s,x)\delta(s, x) 最短路径的边数
cnt(s)=0\text{cnt}(s) = 0
更新d(y)d(x)+zd(y) \leftarrow d(x) + z 时,同时更新cnt(y)=cnt(x)+1\text{cnt}(y) = \text{cnt}(x) + 1
如果发现cnt(y)n\text{cnt}(y) \geqslant n,图中有负环

分层图解决有后效性 dp

Telephone Lines

利用动态规划的思想,dp(x,p)dp(x, p) 表示从1x1 \to x,指定pp 条电缆免费,此时所需的最小花费

  • (x,y)(x, y) 不免费,dp(y,p)=min(dp(y,p),max(dp(x,p),z))dp(y, p) = \min(dp(y, p), \max(dp(x, p), z)),其中z=w(x,y)z = w(x, y)
  • (x,y)(x, y) 免费,dp(y,p+1)=dp(x,p)dp(y, p+1) = dp(x, p)

观察状态转移方程发现,存在转移
dp(x,p)zdp(y,p), dp(x,p)dp(y,p+1)dp(x, p) \xrightarrow{z} dp(y, p), \ dp(x, p) \to dp(y, p+1)

如果仅有dp(x,p)dp(y,p+1)dp(x, p) \to dp(y, p+1) 的转移,直接用dp\text{dp} 求解是没问题的
但这里可能存在dp(x,p)zdp(y,p)dp(yk,p)zkdp(x,p)dp(x, p) \xrightarrow{z} dp(y, p) \to \cdots dp(y_k, p) \xrightarrow{z_k} dp(x, p)
可能存在环路,不符合dp\text{dp} 状态空间转移构成有向无环图的条件

但可以利用spfa\text{spfa},将二元组哈希成一个点
(x,p),(y,p)(x, p), (y, p) 连长度为zz 的边,(x,p),(y,p+1)(x, p), (y, p+1) 连一条长度为00 的边
(1,0)(1, 0) 开始执行spfa\text{spfa},将所有点初始化成d(u)=d(u) = \infty
对于边(u,v,z)(u, v, z),每次执行更新d(v)=min(d(v),max(d(u),z))d(v) = \min (d(v), \max (d(u), z))
最后d(n,K)d(n, K) 就是答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
const int maxn = 2e6 + 10, inf = 0x3f3f3f3f;
const int maxm = 5e6 + 10;
int n, m, K;

namespace Graph {
int idx = 1;
int head[maxn], ver[maxm], e[maxm], ne[maxm];

void initG() {
idx = 1;
memset(head, 0, sizeof head);
}

void add(int a, int b, int c) {
ver[++idx] = b, e[idx] = c, ne[idx] = head[a], head[a] = idx;
}
}

using namespace Graph;

inline int get(int x, int y) {
return x + n*y;
}

int d[maxn], inq[maxn];
void spfa(int s) {
queue<int> q;
memset(d, inf, sizeof d);
memset(inq, 0, sizeof inq);
d[s] = 0, inq[s] = 1;
q.push(s);

while (q.size()) {
auto u = q.front(); q.pop();
inq[u] = 0;

for (int i = head[u]; i; i = ne[i]) {
int v = ver[i];
if (d[v] > max(d[u], e[i])) {
d[v] = max(d[u], e[i]);
if (!inq[v]) q.push(v), inq[v] = 1;
}
}
}
}

int main() {
freopen("input.txt", "r", stdin);
scanf("%d%d%d", &n, &m, &K);
initG();

while (m--) {
int a, b, l;
scanf("%d%d%d", &a, &b, &l);

for (int i = 0; i <= K; i++) {
int u = get(a, i), v = get(b, i);
add(u, v, l), add(v, u, l);
}
for (int i = 0; i < K; i++) {
add(get(a, i), get(b, i+1), 0);
add(get(b, i), get(a, i+1), 0);
}
}

spfa(get(1, 0));
int ans = d[get(n, K)];
if (ans == inf) puts("-1");
else printf("%d\n", ans);
}

spfa 和 dp

spfa 的思想和 dp 有很类似的地方,dp 中的状态转移方程dp(y)=dp(x)+f(x,y)dp(y) = dp(x) + f(x, y)
用 spfa 算法可以让转移方程收敛到最优

最优贸易

根据dp\text{dp} 思想,对于某个点yy,用dp(y)dp(y) 表示从1y1 \to y 路径上经过权值最小的点
dp(y)dp(y) 必然是从yy 的前驱节点转移过来的,前驱节点集合不妨记为π(y)\pi (y)

dp(y)=min(dp(y),minxπ(y)(dp(x),cost(y)))dp(y) = \min(dp(y), \min_{x \in \pi(y)}(dp(x), cost(y)))

这样对于任意节点uudp(u)dp(u) 即可知道1u1\to u 路径中最小花费的城市所需的代价
接下来只要求出unu \to n 路径中最大花费的城市即可

思路是类似的,建一张从n1n \to 1 的反图,执行spfa(n)\text{spfa}(n),转移方程为

dp2(y)=max(dp2(y),maxxπ(y)(dp2(x),cost(y)))dp2(y) = \max(dp2(y), \displaystyle \max_{x \in \pi(y)}(dp2(x), cost(y)))

最后枚举每个节点uu,计算max(dp2(u)dp(u))\max (dp2(u) - dp(u))

1
2
3
4
add1() 表示添加正向图,add2() 表示反向图

对于单向边 (x, y),执行 add1(x, y), add2(y, x)
如果是双向边 (x, y),还要补上缺少的部分,add1(y, x), add2(x, y)

Dijkstra 和最短路树

Dijkstra\text{Dijkstra} 算法可以求出最短路树,只需要Relax\text{Relax} 操作时,只要
d(i)+w(i,j)<d(j)d(i) + w(i, j) < d(j) 更新d(j)d(j) 时,同时令p(j)=ip(j) = i,这样把pp 看成是父指针,
起点的p(s)=sp(s) = s,其他每个点对应一条边p(u)up(u) \to u

dijkstra\text{dijkstra}vis(u)\text{vis}(u) 数组表示uu 这个节点是否被扩展过
spfa\text{spfa}inq(u)\text{inq}(u) 表示uu 是否在队列中

Warfare and Logistics

对于GG 中的任意原点s\forall s,都可以用dijkstra(s)\text{dijkstra}(s) 求出任意节点iVi \in V 的最短路,记为

δ(s,i)=d(i)\delta(s, i) = d(i),以ss 为源点,所有点的最短路径和记为C(s)=i=1nd(i)C(s) = \displaystyle \sum_{i = 1}^{n} d(i)

本例令res=s=1nC(s)res = \displaystyle\sum_{s = 1}^{n} C(s),要求删除一条边之后,使得新的resres' 最大

源点为ss 的单源最短路,生成的最短路树不妨表示为前驱子图Vπ(s)V_{\pi}(s)
最短路树以ss 为根,如果删除的边e∉Vπ(s)e \not\in V_{\pi}(s),最短路值都不会发生改变
Vπ(s)V_{\pi}(s) 上恰好有nn 个点n1n-1 条边

所以只需要枚举最短路树上的边,尝试删除并重新计算最短路,取一个max\max 即可

  • 如果删除的边e∉Vπ(s)\forall e \not\in V_{\pi}(s),那么C(s)C(s) 值不变
  • 否则,eVπ(s)e \in V_{\pi}(s),需要重新计算最短路dijkstra(s)\text{dijkstra}(s),并且求出新的C[s]=i=1nd(i)C[s] = \displaystyle \sum_{i = 1}^{n} d(i)

具体到算法实现上

  1. 对每个源点s[1,n]s \in [1, n] 初始化d(i)=+,p(i)=0d(i) = +\infty, p(i) = 0 并且dijkstra(s)\text{dijkstra}(s) 得到d(i),p(i)d(i), p(i)

    C[s]+=i=1nd(i)C[s] += \displaystyle\sum_{i = 1}^{n} d(i)

    然后执行dfs(s)\text{dfs}(s),对{(u,v): p(v)=u}\{(u, v): \ p(v) = u\} 的边标记为必须边,mark(s,u,v)=1\text{mark}(s, u, v) = 1

  2. 枚举最短路树上的边,其实是枚举每个点对(i,j)(i, j)
    对于边(i,j)(i, j),枚举每个顶点ss,如果(i,j)(i, j)Vπ(s)V_{\pi}(s) 的树边,将w(i,j)=0w(i, j) = 0
    重新计算dijkstra(s)\text{dijkstra}(s),并且将结果res+=d(i)res += \sum d(i),否则的话直接res+=C[s]res += C[s]
    计算完之后记得还原现场,对resres 求一个max\max 即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
const int inf = 0x3f3f3f3f;
const int maxn = 100 + 10, maxm = 2000 + 10;
int n, m, L;
vector<int> edges[maxn][maxn];
int ID[maxn][maxn];
typedef pair<int, int> PII;

namespace Graph {
int idx = 1;
int head[maxn], ver[maxm], ne[maxm], e[maxm];
void initG() {
idx = 1;
memset(head, 0, sizeof head);
memset(ID, 0, sizeof ID);
_for(i, 0, maxn) _for(j, 0, maxn) edges[i][j].clear();
}

void add(int a, int b, int c) {
ver[++idx] = b, e[idx] = c, ne[idx] = head[a], head[a] = idx;
ID[a][b] = idx;
}

int d[maxn], p[maxn], vis[maxn];
void dijkstra(int s) {
memset(d, inf, sizeof d);
memset(p, 0, sizeof p);
memset(vis, 0, sizeof vis);

d[s] = 0;
priority_queue<PII, vector<PII>, greater<PII> > q;
q.push({0, s});

while (q.size()) {
auto u = q.top(); q.pop();
int x = u.second;

if (vis[x]) continue;
vis[x] = true;

for (int i = head[x]; i; i = ne[i]) {
int y = ver[i];
if (e[i] > 0 && d[y] > d[x] + e[i]) {
d[y] = d[x] + e[i], p[y] = x;
q.push({d[y], y});
}
}
}
}
}
using namespace Graph;
ll C[maxn];
int mark[maxn][maxn][maxn];

void get_mark(int s) {
for (int i = 1; i <= n; i++) {
if (p[i] == 0) continue;
mark[s][i][p[i]] = mark[s][p[i]][i] = 1;
}
}

void calc() {
memset(C, 0, sizeof C);
memset(mark, 0, sizeof mark);

for (int s = 1; s <= n; s++) {
dijkstra(s);
get_mark(s);
for (int i = 1; i <= n; i++) C[s] += d[i] == inf ? L : d[i];
}

ll sum = 0;
for (int s = 1; s <= n; s++) sum += C[s];
printf("%lld ", sum);
}

ll del(int i, int j) {
ll sum = 0;
int id = ID[i][j];

if (edges[i][j].size() == 1) e[id] = e[id^1] = 0;
else if (edges[i][j].size() > 1) e[id] = e[id^1] = edges[i][j][1];

for (int s = 1; s <= n; s++) {
if (mark[s][i][j] == 0) sum += C[s];
else {
dijkstra(s);
for (int u = 1; u <= n; u++) sum += d[u] == inf ? L : d[u];
}
}

e[id] = e[id^1] = edges[i][j][0];
return sum;
}

int main() {
freopen("input.txt", "r", stdin);
while (scanf("%d%d%d", &n, &m, &L) == 3) {
initG();

while (m--) {
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
edges[a][b].push_back(c), edges[b][a].push_back(c);
}

// add
for (int i = 1; i <= n; i++) for (int j = i+1; j <= n; j++) {
if (edges[i][j].size() == 0) continue;
sort(edges[i][j].begin(), edges[i][j].end());

add(i, j, edges[i][j][0]), add(j, i, edges[i][j][0]);
}

// calc
calc();

ll res = 0;
for (int i = 1; i <= n; i++) for (int j = i+1; j <= n; j++) {
if (edges[i][j].size() == 0) continue;
res = max(res, del(i, j));
}
printf("%lld\n", res);
}
}

dijkstra 和拓扑排序

SPFA 算法复杂度最坏可能达到O(nm)O(nm),在某些特殊构造的图上会超出时限
道路与航线

对于dijkstra\text{dijkstra} 算法,在非负权的连通块中,从起点ss 总能找到一条最短路
注意到本例中只有航线是负权,并且航线形成的路径是一个DAG\text{DAG}
由此可以设计出如下算法

一开始只加入正权边,然后这些边形成正权连通块,将连通块缩点
再加入负权边,负权边和连通块构成了新的 DAG,在 DAG 上用拓扑排序或者 dp
对于连通块,拓扑序为cc1cc2cc_1\to cc_2,可知d(cc2)=min(d(cc2),d(cc1)+w(cc1,cc2))d(cc_2) = \min (d(cc_2), d(cc_1) + w(cc_1, cc_2))
而对于连通块cc1cc_1 而言,假设起点为ss,执行dijkstra(s)\text{dijkstra}(s)
可以快速求出任意节点的最短路d(y)=δ(s,y)d(y) = \delta (s, y)
对于横跨连通块的边界点,放入拓扑队列中,依次进行dijkstra\text{dijkstra} 松弛,最后dd 数组就是答案

具体来说

  1. 只加入正权边,然后对所有点 xG\forall \ x \in G 执行dfs\text{dfs} 找连通块[1cnt][1\cdots cnt],得到c[x]c[x]
    表示xx 属于哪个连通块
  2. 加入负权边(x,y)(x, y),如果c[x]c[y]c[x] \neq c[y],那么++deg(c[y])++\text{deg}(c[y])
  3. 主算法执行拓扑序 dp,用队列qq 维护连通块拓扑序
    • 找到deg[cc]=0\text{deg}[cc] = 0 的连通块cccc,入队列q[]ccq[\cdots] \leftarrow cc,不要忘了初始化dd 数组
      d[]=, d(S)=0d[\cdots] = \infty, \ d(S) = 0
    • while q[]:ccq.front()\textbf{while} \ q[\cdots] \neq \emptyset: \quad cc \leftarrow q.\text{front}()
      扫描所有的点uV\forall u \in V,对于c[u]=ccc[u] = cc 的点,插入heap\text{heap}
      while heap\textbf{while} \ \text{heap} \neq \emptyset,执行堆优化的dijkstra\text{dijkstra}
      注意这里对每个连通块局部进行dijkstra\text{dijkstra},检查每条边(x,y)(x, y)
      只对正权边使用dijkstra\text{dijkstra}堆只维护c[x]=c[y]c[x] = c[y] 的边(x,y)(x, y)
      d(y)<d(x)+e(x,y)\quad d(y) < d(x) + e(x, y) 的时候,更新d(y)d(y)c[x]=c[y]c[x] = c[y]yy 入堆
    • 检查(x,y): c[x]c[y] and deg(c[y])=0(x, y): \ c[x] \neq c[y] \ \textbf{and} \ --\text{deg}(c[y]) = 0,将q[]c[y]q[\cdots] \leftarrow c[y] 入队列
      此时c[y]c[y] 作为下个拓扑序连通块
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
typedef pair<int, int> PII;
const int maxn = 25000 + 10, inf = 0x3f3f3f3f;
const int maxm = 2e5 + 10;

int n, R, P, S;

namespace Graph {
int idx = 1, cnt = 0;
int head[maxn], ver[maxm], e[maxm], ne[maxm], C[maxn], deg[maxn];

void initG() {
idx = 1;
cnt = 0;
memset(head, 0, sizeof head);
memset(C, 0, sizeof C);
memset(deg, 0, sizeof deg);
}

void add(int a, int b, int c) {
ver[++idx] = b; e[idx] = c; ne[idx] = head[a]; head[a] = idx;
}

void dfs(int u) {
C[u] = cnt;
for (int i = head[u]; i; i = ne[i]) {
int v = ver[i];
if (C[v]) continue;
dfs(v);
}
}

void dfs() {
for (int i = 1; i <= n; i++) {
if (!C[i]) {
++cnt;
dfs(i);
}
}
}
}

using namespace Graph;

int d[maxn], vis[maxn];
void solve() {
memset(d, inf, sizeof d);
memset(vis, 0, sizeof vis);
d[S] = 0;

queue<int> q;
for (int i = 1; i <= cnt; i++) if (deg[i] == 0) q.push(i);

while (q.size()) {
auto cc = q.front(); q.pop();

priority_queue<PII, vector<PII>, greater<PII> > heap;
for (int i = 1; i <= n; i++) if (C[i] == cc) heap.push({d[i], i});

while (heap.size()) {
int x = heap.top().second; heap.pop();
if (vis[x]) continue;
vis[x] = true;

for (int i = head[x]; i; i = ne[i]) {
int y = ver[i];
if (C[y] != C[x] && --deg[C[y]] == 0) q.push(C[y]);
if (d[y] > d[x] + e[i]) {
d[y] = d[x] + e[i];
if (C[x] == C[y]) heap.push({d[y], y});
}
}
}
}
}

int main() {
freopen("input.txt", "r", stdin);
cin >> n >> R >> P >> S;
initG();

// add +
while (R--) {
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a, b, c), add(b, a, c);
}

// dfs
dfs();

// add -
while (P--) {
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a, b, c);
if (C[a] != C[b]) ++deg[C[b]];
}

// solve
solve();

for (int i = 1; i <= n; i++) {
if (d[i] >= 1e9) puts("NO PATH");
else printf("%d\n", d[i]);
}
}