多源最短路径算法：Floyd算法
前言
由于本人太菜，这里不讨论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)\)。
版权声明：本文为lingfunny原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。