文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 高等教育 > 工学 > Floyd算法详解
侵权投诉

Floyd算法详解

求最短路径算法总结

标签: 分类: 数据结构

floyd算法

it

部分内容参考 doc.guandang.net

All-Pairs 的最短路径问题:所有点对之间的最短路径

Dijkstra算法是求单源最短路径的,那如果求图中所有点对的最短路径的话则有以下两种解法:

解法一:

以图中的每个顶点作为源点,调用Dijkstra算法,时间复杂度为O(n3);

解法二:

Floyd(弗洛伊德算法)更简洁,算法复杂度仍为O(n3)。

n

正如大多数教材中所讲到的,求单源点无负边最短路径用Dijkstra,而求所有点最短路径用Floyd。确实,我们将用到Floyd算法,但是,并不是说所有情况下Floyd都是最佳选择。 对于没有学过Floyd的人来说,在掌握了Dijkstra之后遇到All-Pairs最短路径问题的第一反应可能会是:计算所有点的单源点最短路径,不就可以得到所有点的最短路径了吗。简单得描述一下算法就是执行n次Dijkstra算法。

Floyd可以说是Warshall算法的扩展了,三个for循环便可以解决一个复杂的问题,应该说是十分经典的。从它的三层循环可以看出,它的复杂度是n3,除了在第二层for中加点判断可以略微提高效率,几乎没有其他办法再减少它的复杂度。

比较两种算法,不难得出以下的结论:对于稀疏的图,采用n次Dijkstra比较出色,对于茂密的图,可以使用Floyd算法。另外,Floyd可以处理带负边的图。

下面对Floyd算法进行介绍:

Floyd算法的基本思想:

可以将问题分解,先找出最短的距离,然后在考虑如何找出对应的行进路线。如何找出最短路径呢,这里还是用到动态规划的知识,对于任何一个城市而言,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之间的最短距离了。

Floyd算法的基本步骤:

定义n×n的方阵序列D-1, D0 , … Dn-1,

初始化: D-1=C

D-1[i][j]=边<i,j>的长度,表示初始的从i到j的最短路径长度,即它是从i到j的中间不经过其他中间点的最短路径。

迭代:设Dk-1已求出,如何得到Dk(0≤k≤n-1)?

Dk-1[i][j]表示从i到j的中间点不大于k-1的最短路径p:i…j,

考虑将顶点k加入路径p得到顶点序列q:i…k…j,

若q不是路径,则当前的最短路径仍是上一步结果:Dk[i][j]= Dk-1[i][j];

否则若q的长度小于p的长度,则用q取代p作为从i到j的最短路径。

第1页

你可能喜欢

  • 弗洛伊德算法
  • 迪杰斯特拉算法
  • 最短路径算法
  • 蚁群算法 matlab
  • Dijkstra算法代码
  • Excel使用技巧大全(超
  • 最小生成树算法

热门文档

相关文档

  • 数学建模最短路算法:floyd算法详解

    数学模型与实验 最短 路 算 法 任意一对顶点之间的最短路算法:Floyd算法 lzb8401552@hgnu.edu.cn 数学模型与实验 (一)算法的基本思想 (二)算 法原理 1、求...

  • Floyd算法详解:求解任意两点间的最短距离

    Floyd算法详解:求解任意两点间的最短距离_工作计划_计划/解决方案_实用文档。Floyd-Warshall 算法,简称 Floyd 算法,用于求解任意两点间的最短距离,时间复杂度为 O...

  • Floyd算法

    Floyd 算法——针对带权、有向、连通图,求其所有顶点之间的最短路径 6 2 3 0 9 5 8 3 2 1 图-1 1 一、 问题的提法已知一个各边权值均正整数的带权...

  • 图论模型(floyd算法)

    数学模型与实验 最短 路算 法 任意一对顶点之间的最短路算法:Floyd算法 任意一对顶点之间的最短路算法:Floyd算法 :Floyd lzb8401552@hgnu.edu.cn 数学模型与实验...

  • Floyd算法

    Floyd算法_IT/计算机_专业资料。Floyd 算法核心思路矩阵求出它的每两点间的最短路径矩阵 通过一个图的权值 矩阵 求出它的每两点间的最短路径矩阵 从图的带权...

  • Floyd算法思想及操作详解

    Floyd算法思想及操作详解_数学_自然科学_专业资料。Floyd算法思想描述简单清晰,易于理解,附程序代码。内部资料拿出来共享,帮助大家学习!...

  • Floyd算法

    Floyd算法_天文/地理_自然科学_专业资料。Floyd 算法 Floyd 算法又称为弗洛伊德算法,插点法,是一种用于寻找给定的加 权图中顶点间最短路径的算法。 核心思路:...

  • floyd算法

    所有点对最短路径问题:求每对点间的最短路经 Hu Junfeng 34 Floyd算法 All ... Floyd算法详解:求解任意... 4页 1下载券 用floyd算法求最短距离 ... 2页...

  • floyd算法

    floyd算法_IT/计算机_专业资料。最短路径的算法7.6.2每一对顶点间的最短路径 Dijkstra算法是求源点到其它顶点的最短路 径。怎样求任意两个顶点之间的最短...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email