Floyed

作者: 桐桑入梦 | 来源:发表于2019-12-07 00:28 被阅读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之后使得路径变短了,那么修改路径

    相关文章

      网友评论

          本文标题:Floyed

          本文链接:https://www.haomeiwen.com/subject/ciuygctx.html