floyd-warshanll算法是什么啊
作者&投稿：利萱 （若有异议请与网页底部的电邮联系）
Floyd算法又称为弗洛伊德算法，插点法，是一种用于寻找给定的加权图中顶点间最短路径的算法。通过一个图的权值矩阵求出它的每两点间的最短路径矩阵。 从
这是由其算法本身所决定的，其每一步求出任意一对顶点之间仅通过中间节点1,2,...,k的最短距离，当1,2,...,k扩展到所有顶点时，算法解出任意一对顶点间的最短距离，故顺序自然是：
for(k=1;k<n;++k)
//枚举任意一对顶点
由其状态转移方程来看，这个算法的顺序也很清晰，应该是先计算较小的k时任意ij之间的最短距离：
dij(k) = wij 如果k=0
min(dij(k-1),dik(k-1)+dkj(k-1)) 如果k>=1
其中i,j表示点对，k表示第1,2,...,k时的最短路径
Floyd-Warshall算法的描述如下： for k:=1 to n do for i:=1 to n do for j:=1 to n do if dist[i,k]+dist[k,j]<dist[i,j] then dist[i,j]:=dist[i,k]+dist[k,j];
Floyd-Warshall 算法用来找出每对点之间的最短距离。它需要用邻接矩阵来储存边，这个算法通过考虑最佳子路径来得到最佳路径。
注意单独一条边的路径也不一定是最佳路径。
从任意一条单边路径开始。所有两点之间的距离是边的权，或者无穷大，如果两点之间没有边相连。
对于每一对顶点 u 和 v，看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比己知的路径更短。如果是更新它。
不可思议的是，只要按排适当，就能得到结果。 // dist(i,j) 为从节点i到节点j的最短距离 For i←1 to n do For j←1 to n do dist(i,j) = weight(i,j) For k←1 to n do // k为“媒介节点” For i←1 to n do For j←1 to n do if (dist(i,k) + dist(k,j) < dist(i,j)) then // 是否是更短的路径？ dist(i,j) = dist(i,k) + dist(k,j)
这个算法的效率是O(V^3)。它需要邻接矩阵来储存图。
这个算法很容易实现，只要几行。
即使问题是求单源最短路径，还是推荐使用这个算法，如果时间和空间允许(只要有放的下邻接矩阵的空间，时间上就没问题)。
计算每一对顶点间的最短路径（floyd算法）
【例题】设计公共汽车线路(1) 现有一张城市地图，图中的顶点为城市，有向边代表两个城市间的连通关系，边上的权即为距离。现在的问题是，为每一对可达的城市间设计一条公共汽车线路，要求线路的长度在所有可能的方案里是最短的。
输入： n (城市数，1≤n≤20) e (有向边数1≤e≤210) 以下e行，每行为边（i,j）和该边的距离wij（1≤i,j≤n）
输出： k行，每行为一条公共汽车线路
分析：本题给出了一个带权有向图，要求计算每一对顶点间的最短路径。这个问题虽然不是图的连通性问题，但是也可以借鉴计算传递闭包的思想：在枚举途径某中间顶点k的任两个顶点对i和j时，将顶点i和顶点j中间加入顶点k后是否连通的判断，改为顶点i途径顶点k至顶点j的路径是否为顶点i至顶点j的最短路径（1≤i，j，k≤n）。 显然三重循环即可计算出任一对顶点间的最短路径。设 n—有向图的结点个数； path—最短路径集合。其中path[i，j]为vi至vj的最短路上vj的前趋结点序号(1≤i，j≤n)； adj—最短路径矩阵。初始时为有向图的相邻矩阵
我们用类似传递闭包的计算方法反复对adj矩阵进行运算，最后使得adj成为存储每一对顶点间的最短路径的矩阵 (1≤i，j≤n) Var adj：array[1‥n，1‥n] of real； path：array[1‥n，1‥n] of 0‥n；
计算每一对顶点间最短路径的方法如下：
首先枚举路径上的每一个中间顶点k（1≤k≤n）；然后枚举每一个顶点对（顶点i和顶点j，1≤i，j≤n）。如果i顶点和j顶点间有一条途径顶点k的路径，且该路径长度在目前i顶点和j顶点间的所有条途径中最短，则该方案记入adj[i，j]和path[i，j] adj矩阵的每一个元素初始化为∞；
for i←1 to n do {初始时adj为有向图的相邻矩阵，path存储边信息} for j←1 to n do if wij<>0 then begin adj[i，j]←wij； path[i，j]←j； end{then} else path[i，j]←0； for k←1 to n do {枚举每一个中间顶点} for i←1 to n do {枚举每一个顶点对} for j←1 to n do if adj[i，k]+adj[k，j]<adj[i，j] {若vi经由vk 至vj的路径目前最优，则记下} then begin adj[i，j]←adj[i，k]+adj[k，j]； path[i，j]←path[k，j]； end，{then} 计算每一对顶点间最短路径时间复杂度为W(n3)。算法结束时，由矩阵path可推知任一结点对i、j之间的最短路径方案是什么 Procedure print(i，j)； begin if i=j then 输出i else if path[i，j]=0 then 输出结点i与结点j之间不存在通路 else begin print (i，path[i，j])； {递归i顶点至j顶点的前趋顶点间的最短路径} 输出j； end；{else} end；{print} 由此得出主程序 距离矩阵w初始化为0； 输入城市地图信息（顶点数、边数和距离矩阵w）； 计算每一对顶点间最短路径的矩阵path； for i←1 to n do {枚举每一个顶点对} for j←1 to n do if path[i，j]<>0 {若顶点i可达顶点j，则输出最短路径方案} then begin print（i，j）； writeln； end；{then}
羽购因卡：[答案] #include const int MAX=100; int g[MAX][MAX]; void floyd(int n)///弗洛易德算法 { int i,j,k; for(k=0;k
左权县17243844251： 顶点之间的最短路径(Floyd)算法 - ？
羽购因卡：#include<stdio.h> #define INFINITE 9999 //无穷,或是不能到达的顶点 #define V_N 6 //6个顶点 #define E_N 10 //8条边 #define ALL_N V_Nint graph_matrix[V_N+1][V_N+1]; //下标从1开始,图数组int distance[V_N+1][V_N+1]; //下标从1开始...
左权县17243844251： 浮力的计算方法:称量法:F浮 = - ---- - 平衡法:F浮 =----- - ( - ？
羽购因卡： 称量法:F浮 =G-F拉 平衡法:F浮 =G物(悬浮或漂浮)阿基米德远原理法:F浮=G排=m排g=ρ液gV排不明追问.
左权县17243844251： 关于MATLAB.floyd算法的求助 - ？
羽购因卡： 这个是M文件中的函数啊,只有运行在主界面并且这样运行: floyd(a)(把a输入括号这里才行) 单独运行当然没有定义a啊%floyd.m %采用floyd算法计算图a中每对顶点最短路 %d是矩离矩阵 %r是路由矩阵 function [d,r]=floyd(a) n=size(a,1); d=a; for ...
左权县17243844251： JVM有哪些垃圾回收算法? - ？
羽购因卡： 1.Mark-Sweep(标记-清除)算法 这是最基础的垃圾回收算法,之所以说它是最基础的是因为它最容易实现,思想也是最简单的.标记-清除算法分为两个阶段:标记阶段和清除阶段.标记阶段的任务是标记出所有需要被回收的对象,清除阶段就...
左权县17243844251： 图像缩放的放大算法 - ？
羽购因卡： 图像放大几乎都是采用内插值方法,即在原有图像像素的基础上在像素点之间采用合适的插值算法插入新的元素. 对插值算法分类比较混乱,各人有各人的分类算法.文献《图像插值技术综述》 中简略的将插值算法分为传统插值、 基于边缘的...
左权县17243844251： 简述下降迭代算法构成的基本步骤? - ？
羽购因卡： 下降迭代算法构成的基本步骤 (1)给定一个初始点X(0)和收敛精度ε (2)选取一个搜索方向S(k) (3)确定步长因子ak,按上式得到新的迭代点 (4)收敛判断:若X(k+1)满足收敛精度,则以X(k+1)作为最优点,终止计算;否则,以X(k+1)作为新的起点,转2)进行下一轮迭代.
左权县17243844251： 常用的导航/路径规划软件都用到哪些算法 - ？
羽购因卡： Dijkstra算法(荷兰语读作“戴克斯的”),在百度百科上搜“迪杰斯特拉算法”就能看到.此外,还有非官方的SPFA算法,两种都很快.Dijkstra的思想如下:在有向无负权图上跑,首先,起点到起点最短路径为0,是固定的.把起点向四周扩展,得到四周的“准最短路长”.再选择一个未固定且“准最短路长”最短的点,固定它,再扩展它(如果扩展出来的其它点的新的“准最短路长”小于旧的“准最短路长”,就把它更新,否则不更新).因为它的“准最短路长”是未固定的点中最短的,所以不可能从别的未固定的点更新它的最短路长.如此,再选择一个未固定且“准最短路长”最短的点,固定它,再扩展它......
左权县17243844251： 几种常用的算法简介 - ？
羽购因卡： 1、穷举法穷举法是最基本的算法设计策略,其思想是列举出问题所有的可能解,逐一进行判别,找出满足条件的解. 穷举法的运用关键在于解决两个问题: 在运用穷举法时,容易出现的问题是可能解过多,导致算法效率很低,这就需要对列举...
左权县17243844251： 起泡排序和冒泡排序是不是一个概念 - ？
羽购因卡： C实现冒泡排序算法 最简单的排序方法是冒泡排序方法.这种方法的基本思想是,将待排序的元素看作是竖着排列的“气泡”,较小的元素比较轻,从而要往上浮.在冒泡排序算法中我们要对这个“气泡”序列处理若干遍.所谓一遍处理,就...
