想把 spfa 换成 dij,用 Johnson 里面的技巧,给予每个点一个势能 \(h_u\),边 \((u,v,w)\) 的新边权为 \(w+h_u-h_v\),为了保证其 \(\geq 0\) 以源点为最短路跑最短路后赋值 \(h_u\gets d_u\) 即可。
增广之后会加入反向边,考虑怎么更新势能。首先一条边的反向边被加入,其满足什么条件,然后推推式子(这里令 \(d'\) 为以 \(h\) 作为势能的最短路):
\(d'_u+w_{u,v}+h_u-h_v=d'v\)
将同类型的合并:
\((d'_u+h_u)-(d'_v+h_v)+w_{u,v}=0\)
有 \(w_{u,v}=-w_{v,u}\) 所以 \((d'_u+h_u)-(d'_v+h_v)=w_{v,u}\)
此时发现如果将新的势能 \(h'_u\gets d'_u+h_u\) 即满足反向边 \(=0\),再来验证一下原先就存在的边:
根据三角形不等式 \(d'_u+w_{u,v}+h_u-h_v\geq d'v\)
从而也有
\(w_{u,v}+(d'_u+h_u)-(d'_v+h_v)\geq 0\)