Dijkstra实现费用流

Posted on Edited on In Views:
Symbols count in article: 282 Reading time ≈ 1 mins.
我非要用Dijkstra

  1. 用SPFA求出源点到每个点的最短距离

  2. 为每个点 i 赋点权 h[i]为dis[i] ,并视每条连接 u,v 的边 i 的边权 w’[i] 为 w[i]+h[u]-h[v] 。

    由于对于任意两点 u,v ,有w[u][v]+h[u]-h[v]≥0 ,所以 w’ [i]≥0 ,这样一来新图上的 dis’[i] 就等于** dis[i]+h[S]-h[i]**。

    由于每次跑最短路时 h[i] 都是不变的,所以求出了 dis’[i] 也就求出了 dis[i] ( dis[i]=dis’[i]-h[S]+h[i] ,其实很显然 h[S]=0 )

graph LR;
	u((u))
	v((v))
	u--"w[u][v]+h[u]-h[v]"-->v