【模板】多源最短路径(Floyd算法)

动态规划思想:用d[i][j][k]表示“若只经过编号为1~k的节点(除了起点和终点),从节点i到节点j的最短路径的长度”。d[i][j][k]=min{d[i][j][k-1],d[i][k][k-1]+d[k][j][k-1]},借用背包问题的思想,d[i][j][k]只继承d[][][k-1]或从d[][][k-1]更新,所以可以舍弃[k]这一维。d[i][j]初始化为i->j的边权(若无边则为无穷大,若i=j则为0)。

主代码段如下:

注意:k这一维必须置于循环的最外侧,因为在“只经过1~k个节点的路径长度”更新时,使用的数据必须是“只经过1~k-1个节点的最短路径长度”,所以在第k轮更新时,第k-1轮必须已经完全更新结束。

Subscribe
提醒
guest
1 评论
Oldest
Newest Most Voted
Inline Feedbacks
View all comments
cyx
cyx
2020年8月20日 上午9:10

得不了!