最短路——Floyd – Warshall核心算法的理解

最短路——Floyd – Warshall核心算法的理解

首先,谁能告诉我弗洛伊德的核心算法是什么?

   //核心代码
        for(int k = 1 ; k <= n ; k ++)
        {
                for(int i = 1 ; i <= n ; i ++)
                {
                        for(int j = 1 ; j <= n ; j ++)
                        {
                                if(e[i][j] > e[i][k] + e[k][j])
                                        e[i][j] = e[i][k] + e[k][j];
                        }
                }
        }

就用下面这个例子,来帮助理解吧;

  简介:Floyd算法又称为插点法,是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法,与Dijkstra算法类似。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名

eg:暑假,小哼准备去一些城市旅游。有些城市之间有公路,有些城市之间则没有,如下图。为了节省经费及方便计划旅程,小哼希望在出发前知道任意两个城市之间的最短路程。

    上图中有4个城市8条公路,公路上的数字表示这条公路的长短。请注意这些公路是单向的。我们现在需要求任意两个城市之间的最短路程,也就是求任意两个点之间的最短路径。这个问题这也被称为“多源最短路径”问题。

    现在需要一个数据结构来存储图的信息,我们仍然可以用一个4*4的矩阵(二维数组e)来存储。比如1号城市到2号城市的路程为2,则设e[1][2]的值为2。2号城市无法到达4号城市,则设置e[2][4]的值为∞。另外此处约定一个城市自己是到自己的也是0,例如e[1][1]为0。

最短路——Floyd - Warshall核心算法的理解

 

最短路——Floyd - Warshall核心算法的理解

 

我们回到最开始的问题,最短路径问题,如何求任意两点之间的最短路径呢?

我们通过之前的学习,我们知道通过深搜或者广搜都可以求出两点的最短路径,所以进行n^2 遍深搜或广搜,即对每个点都进行一次深搜或者广搜,我们就可以求得最短路径。但是我们最常用求最短路径的算法的就是bellman-ford,dijkstra,spfa,floyd算法。

如果求任意两点之间的最短路径,两点之间可以直接到达但却不是最短的路径,要让任意两点(例如从顶点a点到顶点b)之间的路程变短,只能引入第三个点(顶点k),并通过这个顶点k中转即a->k->b,才可能缩短原来从顶点a点到顶点b的路程。那么这个中转的顶点k是1~n中的哪个点呢?甚至有时候不只通过一个点,而是经过两个点或者更多点中转会更短。比如上图中从4号城市到3号城市(4->3)的路程e[4][3]原本是12。如果只通过1号城市中转(4->1->3),路程将缩短为11(e[4][1]+e[1][3]=5+6=11)。其实1号城市到3号城市也可以通过2号城市中转,使得1号到3号城市的路程缩短为5(e[1][2]+e[2][3]=2+3=5)。所以如果同时经过1号和2号两个城市中转的话,从4号城市到3号城市的路程会进一步缩短为10。通过这个的例子,我们发现每个顶点都有可能使得另外两个顶点之间的路程变短。好,下面我们将这个问题一般化。

当任意两点之间不允许经过第三个点时,这些城市之间最短路程就是初始路程,如下:

最短路——Floyd - Warshall核心算法的理解

假如现在只允许经过1号顶点,求任意两点的最短路径我们应该怎么求呢??

此时我们只需判断e[i][1] + e[1][j] 是否比e[i][j] 要小即可。我们来说明一下e[i][j] 和 e[i][1] + e[1][j] 表示的是什么意思,e[i][j] 就是便是从I号定点到 j 号顶点之间的路程,e[i][1] + e[1][j] 表示的是从 i 号顶点到 1 号顶点,再从1号顶点到 j 号顶点的路径之和。

在这其中,I是从1~n循环,j也是从1~n循环,具体这一步的实现代码如下。

for(i=1;i<=n;i++)
{
    for(j=1;j<=n;j++)
     {
      if ( e[i][j] > e[i][1]+e[1][j] )
      e[i][j] = e[i][1]+e[1][j];
        }
}

在只允许过 1号顶点的情况下,任意两点之间的路程更新为

最短路——Floyd - Warshall核心算法的理解

通过上图我们发现,在只通过1号顶点中转的情况下,3号和2号顶点(e[3][2])、4号顶点到2号顶点(e[4][2])以及4号顶点到3号顶点(e[4][3])的路程都变短了。

 

//经过1号顶点
for(i=1;i<=n;i++)
   for(j=1;j<=n;j++)
        if (e[i][j] > e[i][1]+e[1][j])
            e[i][j]=e[i][1]+e[1][j];
 
 
//经过2号顶点
for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)
        if (e[i][j] > e[i][2]+e[2][j])
            e[i][j]=e[i][2]+e[2][j];

只允许更新1号和2号顶点的情况下,任意两点之间的路径更新为:

最短路——Floyd - Warshall核心算法的理解

通过上图我们可以看出来,在相比只允许1号顶点进行中转的情况,这里允许通过1号和2号顶点进行中转,使得e[1][3] 和e[4][3]的路程变得更短了。

同理,假如允许所有顶点作为中转,任意两点的最终路程为:

最短路——Floyd - Warshall核心算法的理解
 

整个算法过程虽然说起来很麻烦,但是核心代码就那么几行,不信你看:

for(int k = 1 ; k <= n ; k ++)
{
        for(int i = 1 ; i <= n ; i ++)
        {
                for(int j = 1 ; j <= n ; j ++)
                {
                        if(e[i][j] > r[i][k] + e[k][j])
                                e[i][j] = e[i][k] + e[k][j];
                 }
        }
}

再来分析一下算法:
Floyd优缺点分析:

优点:比较容易容易理解,可以算出任意两个节点之间的最短距离,代码编写简单。
缺点:时间复杂度比较高(n3),不适合计算大量数据,当数据稍微大点儿的时候就可以选择其他的算法来解决问题了,不然也会是超时。

Floyd算法与Dijkstra算法的不同

1.Floyd算法是求任意两点之间的距离,是多源最短路,而Dijkstra(迪杰斯特拉)算法是求一个顶点到其他所有顶点的最短路径,是单源最短路。
2.Floyd算法属于动态规划,我们在写核心代码时候就是相当于推dp状态方程,Dijkstra(迪杰斯特拉)算法属于贪心算法。
3.Dijkstra(迪杰斯特拉)算法时间复杂度一般是o(n^2),Floyd算法时间复杂度是o(n^3),Dijkstra(迪杰斯特拉)算法比Floyd算法块。
4.Floyd算法可以算带负权的,而Dijkstra(迪杰斯特拉)算法是不可以算带负权的。并且Floyd算法不能算负权回路。
 上代码吧:

#include<bits/stdc++.h>
using namespace std;
const int INF = 99999999;
int main()
{
        int e[10][10] , n , m , t1 , t2 , t3;
        cin>>n>>m;  //n表示顶点个数,m表示边的条数
        for(int i = 1 ; i <= n ; i ++)
        {
                for(int j = 1 ; j <= n ; j ++)
                {
                        if(i == j)
                                e[i][j] = 0 ;
                        else
                                e[i][j] = INF;
                }
        }
        for(int i = 1 ; i <= m ; i ++)
        {
                cin>>t1>>t2>>t3;
                e[t1][t2] = t3;
        }
 
        //核心代码
        for(int k = 1 ; k <= n ; k ++)
        {
                for(int i = 1 ; i <= n ; i ++)
                {
                        for(int j = 1 ; j <= n ; j ++)
                        {
                                if(e[i][j] > e[i][k] + e[k][j])
                                        e[i][j] = e[i][k] + e[k][j];
                        }
                }
        }
 	//输出 
        for(int i = 1 ; i <= n ; i ++)
        {
                for(int j = 1 ; j <= n ; j ++)
                {
                        printf("%3d",e[i][j]);
                }
                cout<<endl;
        }
        return 0 ;
}
 
/*
4 8
1 2 2
1 3 6
1 4 4
2 3 3
3 1 7
3 4 1
4 1 5
4 3 12
*/

 

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/114873.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 如何激活成功教程SQLyog 企业版,无限期试用[通俗易懂]

    如何激活成功教程SQLyog 企业版,无限期试用[通俗易懂]如何激活成功教程SQLyog企业版,无限期试用SQLyog是一个功能强大,界面简洁大方的MysqlGUI客户端。截止到这篇博客日期2009-08-15,sqlyog8.13已经释出。其通用版是免费的版本——已经是同类软件的佼佼者了但其打开、关闭软件提示画面,软件界面里灰色的不可用企业功能这是让人心里痒痒!网上也有不少的激活成功教程版,先不管其是否真的完美激活成功教程,这使用激活成功教程的软件总是叫人底气

  • modbus调试工具有哪些(野火多功能调试助手)

    一种成熟的MODBUS调试测试工具助手软件(MThings)免费中文现有MODBUS调测软件种类丰富,基本可以满足日常调测需求,但是面对用户群体对高效灵活友好的进一步需求都存在着差距。MThings是一款全新的标准化MODBUS调测工具,提供主从机一体化操作。全功能覆盖MODBUSPollSlave,功能全网最强。

  • 学生注册idea_学生证怎么绑定身份证

    学生注册idea_学生证怎么绑定身份证一、安装进入官网下载适合自己系统的版本,下载地址:https://www.jetbrains.com/idea/download/#section=windows安装中选择适合本机的64位(32位)版本,其他一直next即可二、激活成功教程先下载jar包JetbrainsCrack.jar,把它放到你认为合适的文件夹内,我直接放在了安装目录C:\ProgramFiles\JetBrai…

  • 中文短文本分类实例六-DCNN(A Convolutional Neural Network for Modelling Sentences)「建议收藏」

    中文短文本分类实例六-DCNN(A Convolutional Neural Network for Modelling Sentences)「建议收藏」一.概述DCNN(AConvolutionalNeuralNetworkforModellingSentences)byNalKalchbrenner等,又是文本分类论文的一力作。”准确表达句子的语义是语言理解的核心”,通过学习机器学习和TextCNN,我们可以知道n-gram特征是NLP文本任务和句子表达的一种重要方法。TextCNN通过不同步长的卷积核(例如2…

  • 《大型网站技术架构》读书笔记一:大型网站架构演化

    思维导图一、大型网站系统特点(1)高并发、大流量:PV流量巨大(2)高可用:7*24小时不间断服务(3)海量数据:文件数目分分钟XXTB(4)用户分布广泛:网络情况复杂(5)安全环境恶劣:

    2021年12月29日
  • Struts的ONGL

    Struts的ONGL

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号