LOADING STUFF...

多源最短路径算法:Floyd算法

技术分享4年前 (2020)更新 技术分享
2,301 0 0

前言

由于本人太菜,这里不讨论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)\)

© 版权声明

相关文章

暂无评论

您必须登录才能参与评论!
立即登录
暂无评论...