Floyed

2019-12-07  本文已影响0人  桐桑入梦

path k 数组中保存的是最短路径经过的顶点,
路径的特点是对于任意的顶点 i j,中间经过的顶点号不超过k
例如
path 2表示任意两个顶点,中间顶过顶点号不超过2的最短路径经过的顶点
path 3表示任意两个顶点,中间顶过顶点号不超过3的最短路径经过的顶点
path 4表示任意两个顶点,中间顶过顶点号不超过4的最短路径经过的顶点
.......

如果 由 path k-1 计算出 path k 的内容呢?
1.首先计算出Ak,比较Ak 和 Ak-1
2.如果发现Ak[i][j] <Ak-1[i][j],说明从顶点i到顶点j的路径加入了顶点k之后使得路径变短了,那么修改路径

上一篇下一篇

猜你喜欢

热点阅读