最长路同理,关键是理解松弛。
不存在环的最短路可以用dp。

Dijkstra

Bellman-Ford

存在负权边时,最短路有可能不存在(存在负权环)。

判断正/负环

SPFA

Floyd

任意两点间最短路

$O(N^3)$

1
2
3
4
5
for(int k=0;k<n;++k)
for(int i=0;i<n;++i)
for(int j=0;j<n;++j)
if(d[i][k]<INF && d[k][j]<INF)
d[i][j]=min(d[i][j],d[i][k]+d[k][j]);

p.s. 注意k在最外层

判断传递闭包

即判断两点间是否连通

1
2
3
4
for(int k=0;k<n;++k)
for(int i=0;i<n;++i)
for(int j=0;j<n;++j)
d[i][j]=d[i][j] || (d[i][k] && d[k][j]);

建模

状态图