前言
由于本人太菜, 这里不讨论 Floyd 的正确性.
简介
多源最短路径, 解决的是求从图中任意两点之间的最短路径的问题.
分析
代码短小精悍, 主要代码只有四行, 直接放上:
- for(int k=1;k<=n;++k)
- for(int i=1;i<=n;++i)
- for(int j=1;j<=n;++j)
- dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
接下来一步一步分析这个算法.
其实这个算法并不难, 首先要知道, dis[i][j]表示的是从点 i 到点 j 的最短路径的长度.
仔细看这个语句: dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
其实, 可以再将它放大, 变成这样:
- if(dis[i][k]+dis[k][j]<dis[i][j])
- dis[i][j]=dis[i][k]+dis[k][j];
这个意思就是说, 如果从点 i 到点 k 的最短路径长度加上点 k 到点 j 的最短路径长度比原来点 i 到点 j 的最短路径长度短, 就把原来 i->j 的最短路径更新.
你可能会说:
诶你这不是 i->k->j 和 i->j 作比较吗, 如果 i->a->b->j 比 i->k->j 更短呢?
这时候, 就要回顾一下我们的 dis 数组的含义了. dis[i][j]只表示点 i 到点 j 的最短路径的长度, 并不是 i->j 的路径的长度. 也就是说, 我们不关心是怎么从 i 走到 j 的 (可能是 i->a->b->j, 也可能是 i->c->j), 但是我们只想知道从 i 到 j 最短需要走多长, 其实这就是 dp(动态规划) 的想法了.
你可能会说:
如果到不了呢?? 那还怎么算?
这就涉及到初始化的问题了.
由于是最短路径问题, 所以如果到不了, 我们可以将 dis[i][j]的值设为 inf(无穷大).
如果能从节点 i 直接走到节点 j(这里是直接走到, 就是 i,j 有一条边相连), 就可以把 dis[i][j]设为这条边的权值.
在重新回顾一下 Floyd 的三重循环:
- for(int k=1;k<=n;++k)
- for(int i=1;i<=n;++i)
- for(int j=1;j<=n;++j)
- //...
其实这个 k, 就是我们不断枚举的中转点. 如果从 i 到 j 经过中转点 k 会更短, 就可以更新.
时间复杂度显而易见:\(O(n^3)\).
来源: https://www.cnblogs.com/lingfunny/p/12825857.html