Floyed

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之后使得路径变短了,那么修改路径

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

  • 数据结构基础温故-5.图(下):最短路径 图的最重要的应用之一就是在交通运输和通信网络中寻找最短路径。例如在交通网...
    mengjz阅读 4,449评论 0 1
  • 图的定义与术语 1、图按照有无方向分为无向图和有向图。无向图由顶点和边构成,有向图由顶点和弧构成。弧有弧尾和弧头之...
    unravelW阅读 3,265评论 0 0
  • 我未来的写作路径规划 经过2个月的练习,慢慢喜欢上了写作。 写作需要积累,需要沉淀。我未来的写作路径规划,对应不同...
    小零露阅读 1,414评论 0 1
  • hi,大家好,这是正玮。 终于决定再再次启用这个快被冻结的号,记录下空窗期学习的日常,最近学python数据分析,...
    刘正玮阅读 1,688评论 0 0
  • 一、定义 在一幅加权有向图中,最短路径是指从顶点s到顶点t的最短路径是所有从s到t的路径中的权重最小者。求解最短路...
    null12阅读 7,414评论 0 4

友情链接更多精彩内容