floyd
1、最短路
2、传递闭包
3、找最小环
4、恰好经过k条边的最短路(倍增)
算法思想基于动态规划
- 状态表示:所有从
i
出发,最终走到j
,且只经过节点编号不超过k
的所有路径 - 属性:路径长度的最小值
- 状态计算:
i -> k -> j
- 所有不包含节点k的路径:
d[k - 1][i][j]
- 所有包含节点k的路径:
d[k][i][j] = min(d[k - 1][i][k]
,d[k - 1][k][j])
- 从
i
到k
和从k
到j
这两段路径相互没有影响,同时取到最小值。路径中的节点只包含1
到k
,所以前半段从1
到k
的路径中只能含有1
到k-1
,后半段同理 - 优化:
d[i][j] = min(d[i][k], d[k][j]);
- 所有不包含节点k的路径: