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

Floyd算法详解

因为q的两条子路径i…k和k…j皆是中间点不大于k-1的最短路径,所以从i到j中间点不大于k的最短路径长度为:

Dk[i][j]=min{ Dk-1[i][j], Dk-1[i][k] +Dk-1[k][j] }

Floyd算法实现:

可以用三个for循环把问题搞定了,但是有一个问题需要注意,那就是for循环的嵌套的顺序:我们可能随手就会写出这样的程序,但是仔细考虑的话,会发现是有问题的。 for(int i=0; i<n; i++)

for(int j=0; j<n; j++)

for(int k=0; k<n; k++)

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

for(int k=0; k<n; k++)

for(int i=0; i<n; i++)

for(int j=0; j<n; j++)

这样作的意义在于固定了k,把所有i到j而经过k的距离找出来,然后象开头所提到的那样进行比较和重写,因为k是在最外层的,所以会把所有的i到j都处理完后,才会移动到下一个k,这样就不会有问题了,看来多层循环的时候,我们一定要当心,否则很容易就弄错了。

接下来就要看一看如何找出最短路径所行经的城市了,这里要用到另一个矩阵P,它的定义是这样的:p(ij)的值如果为p,就表示i到j的最短行经为i->...->p->j,也就是说p是i到j的最短行径中的j之前的最后一个城市。P矩阵的初值为p(ij)=i。有了这个矩阵之后,要找最短路径就轻而易举了。对于i到j而言找出p(ij),令为p,就知道了路径i->...->p->j;再去找p(ip),如果值为q,i到p的最短路径为i->...->q->p;再去找p(iq),如果值为r,i到q的最短路径为i->...->r->q;所以一再反复,到了某个p(it)的值为i时,就表示i到t的最短路径为i->t,就会的到答案了,i到j的最短行径为i->t->...->q->p->j。因为上述的算法是从终点到起点的顺序找出来的,所以输出的时候要把它倒过来。

但是,如何动态的回填P矩阵的值呢?回想一下,当d(ij)>d(ik)+d(kj)时,就要让i到j的最短路径改为走i->...->k->...->j这一条路,但是d(kj)的值是已知的,换句话说,就是k->...->j这条路是已知的,所以k->...->j这条路上j的上一个城市(即p(kj))也是已知的,当然,因为要改走i->...->k->...->j这一条路,j的上一个城市正好是p(kj)。所以一旦发现d(ij)>d(ik)+d(kj),就把p(kj)存入p(ij)。

下面是具体的C代码:

#include <stdio.h>

#include <limits.h>

#include <stdlib.h>

#define MAXSIZE 20

void floyd(int [][MAXSIZE], int [][MAXSIZE], int);

void display_path(int [][MAXSIZE], int [][MAXSIZE], int);

void reverse(int [], int);

void readin(int [][MAXSIZE], int *);

#define MAXSUM(a, b) (((a) != INT_MAX && (b) != INT_MAX) ? \

((a) + (b)) : INT_MAX)

上一页第2页

你可能喜欢

  • 弗洛伊德算法
  • 迪杰斯特拉算法
  • 最短路径算法
  • 蚁群算法 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