Floyd最短路径算法 下载本文

内容发布更新时间 : 2024/12/24 10:20:44星期一 下面是文章的全部内容请认真阅读。

================精选公文范文,管理类,工作总结类,工作计划类文档,欢迎阅读下载==============

Floyd最短路径算法

Floyd最短路径算法 2006-10-20, by leon_jlu 在图论中经常会遇到这样的问题,在一个有向图里,求出任意两个节点之间的最短距离。我们在离散数学、数据结构课上都遇到过这个问题,在计算机网络里介绍网络层的时候好像也遇到过这个问题,记不请了... 但是书本上一律采取的是Dijkstra算法,通过Dijkstra算法可以求出单源最短路径,然后逐个节点利用Dijkstra算法就可以了。不过在这里想换换口味,采取Robert Floyd提出的算法来解决这个问题。下面让我们先把问题稍微的形式化一下: 如果有一个矩阵D=[d(ij)],其中d(ij)>0表示i城市到j城市的距离。若i与j之间无路可通,那么d(ij)就是无穷大。又有d(ii)=0。编写一个程序,通过这个距离矩阵D,把任意两个城市之间的最短与其行径的路

--------------------精选公文范文,管理类,工作总结类,工作计划类文档,感谢阅读下载---------------------

~ 1 ~

================精选公文范文,管理类,工作总结类,工作计划类文档,欢迎阅读下载==============

径找出来。 我们可以将问题分解,先找出最短的距离,然后在考虑如何找出对应的行进路线。如何找出最短路径呢,这里还是用到动态规划的知识,对于任何一个城市而言,i到j的最短距离不外乎存在经过i与j之间的k和不经过k两种可能,所以可以令k=1,2,3,...,n(n是城市的数目),在检查d(ij)与d(ik)+d(kj)的值;在此d(ik)与d(kj)分别是目前为止所知道的i到k与k到j的最短距离,因此d(ik)+d(kj)就是i到j经过k的最短距离。所以,若有d(ij)>d(ik)+d(kj),就表示从i出发经过k再到j的距离要比原来的i到j距离短,自然把i到j的d(ij)重写为d(ik)+d(kj),每当一个k查完了,d(ij)就是目前的i到j的最短距离。重复这一过程,最后当查完所有的k时,d(ij)里面存放的就是i到j之间的最短距离了。所以我们就可以用三个for循环把问题搞定了,但是有一个问题需要注意,那就是for循环的嵌套的顺序:我们可能随手就会写出这样的程

--------------------精选公文范文,管理类,工作总结类,工作计划类文档,感谢阅读下载---------------------

~ 2 ~

================精选公文范文,管理类,工作总结类,工作计划类文档,欢迎阅读下载==============

序,但是仔细考虑的话,会发现是有问

题的。 for(int i=0; i for(int j=0; j for(int k=0; k 问题出在我们太早的把i-k-j的距离确定下来了,假设一旦找到了i-p-j最短的距离后,i到j就相当处理完了,以后不会在改变了,一旦以后有使i到j的更短的距离时也不能再去更新了,所以结果一定是不对的。所以应当象下面一样来写

程序: for(int k=0; k 这样作的意义在于固定了k,把所有i到j而经过k的距离找出来,然后象开头所提到的那样进行比较和重写,因为k是在最外层的,所以会把所有的i到j都处理完后,才会移动到下一个k,这样就不会有问题了,看来多层循环的时候,我

们一定要当心,否则很容易就弄错了。 接下来就要看一看如何找出最短路径所行经的城市了,这里要用到另一个矩阵P,它的定义是这样的:p(ij)的值如果为p,就表示i到j的最短行经为i->...->p->j,也就是说p是i到j的最短行径中的j之

--------------------精选公文范文,管理类,工作总结类,工作计划类文档,感谢阅读下载---------------------

~ 3 ~