floyd算法p表

‘壹’ Floyd算法是什么

Floyd算法又称为弗洛伊德算法，插点法，是一种用于寻找给定的加权图中顶点间最短路径的算法。
通过一个图的权值矩阵求出它的每两点间的最短路径矩阵。
从图的带权邻接矩阵A=[a(i,j)] n×n开始，递归地进行n次更新，即由矩阵D(0)=A，按一个公式，构造出矩阵D(1)；又用同样地公式由D(1)构造出D(2)；……；最后又用同样的公式由D(n-1)构造出矩阵D(n)。矩阵D(n)的i行j列元素便是i号顶点到j号顶点的最短路径长度，称D(n)为图的距离矩阵，同时还可引入一个后继节点矩阵path来记录两点间的最短路径。
采用的是(松弛技术)，对在i和j之间的所有其他点进行一次松弛。所以时间复杂度为O(n^3); 其状态转移方程如下： map[i,j]:=min{map[i,k]+map[k,j],map[i,j]} map[i,j]表示i到j的最短距离 K是穷举i,j的断点 map[n,n]初值应该为0，或者按照题目意思来做。
当然，如果这条路没有通的话，还必须特殊处理，比如没有map[i,k]这条路

‘贰’ p->weight如何对二维数组附值D[i][j]=p->weight这样是错误的

这是一个关于FLOYD算法的应用，对于大多数数据结构书上和网上资料中来说，他们都是在用邻接矩阵来解决FLOYD算法，可是我希望用邻接表来处理这个问题，邻接表占用的空间小，但是编写程序相对复杂一些，希望高手积极回答~邻接表我已经建立好了，就是在附值上出现了问题，非常郁闷~苦思冥想也没想出正确路子~很悲剧~急急急呀!!!!
问题补充：void Floyd(int n,int Q[][maxint],int D[][maxint])//Q为路径D为权值
{
int i,j,k;
arctype *p,*q;
adjlisttype graph;
for(i=1;i<=n;i++)//设置路径长度和路径初值
for(j=1,p=graph[j].firstarc;j<=n,p!=NULL;j++,p=p->nextarc)
{ if(p->weight!=maxint)//<---这里的问题
Q[i][j]=j;//j是i的后继
else
Q[i][j]=0;
D[i][j]=p->weight;//<---这里的问题
}
for(k=1;k<=n;k++)
{//做K次迭代，每次均试图将顶点扩充到当前求得的i到j的最短路径上
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
if(D[i][k]+D[k][j]<D[i][j])
{

‘叁’ 弗洛伊德的算法（Floyd’s algorithm ）

假设这个图的weight matrix存在map[5][5]中，

for(intk=0;k<5;k++)
for(inti=0;i<5;i++)
for(intj=0;j<5;j++)if(i!=j){
if(map[i][k]+map[k][j]<map[i][j])
map[i][j]=map[i][k]+map[k][j];
}

处理完之后map[i][j]存的就是i，j之间的最短路径长度。

简单的说，当执行完一次最外层循环时，map记录的时i，j之间允许使用中间节点｛0, ..., k｝的最短路径。

‘肆’ Floyd算法的参考代码

function Floyd(w,router_direction,MAX)
%w为此图的距离矩阵
%router_direction为路由类型：0为前向路由；非0为回溯路由
%MAX是数据输入时的∞的实际值
len=length(w);
flag=zeros(1,len);
%根据路由类型初始化路由表
R=zeros(len,len);
for i=1:len
if router_direction==0%前向路由
R(:,i)=ones(len,1)*i;
else %回溯路由
R(i,:)=ones(len,1)*i;
end
R(i,i)=0;
end
disp('');
disp('w(0)');
dispit(w,0);
disp('R(0)');
dispit(R,1);
%处理端点有权的问题
for i=1:len
tmp=w(i,i)/2;
if tmp~=0
w(i,:)=w(i,:)+tmp;
w(:,i)=w(:,i)+tmp;
flag(i)=1;
w(i,i)=0;
end
end
%Floyd算法具体实现过程
for i=1:len
for j=1:len
if j==i || w(j,i)==MAX
continue;
end
for k=1:len
if k==i || w(j,i)==MAX
continue;
end
if w(j,i)+w(i,k)<w(j,k) %Floyd算法核心代码
w(j,k)=w(j,i)+w(i,k);
if router_direction==0%前向路由
R(j,k)=R(j,i);
else %回溯路由
R(j,k)=R(i,k);
end
end
end
end
%显示每次的计算结果
disp(['w(',num2str(i),')'])
dispit(w,0);
disp(['R(',num2str(i),')'])
dispit(R,1);
end
%中心和中点的确定
[Center,index]=min(max(w'));
disp(['中心是V',num2str(index)]);
[Middle,index]=min(sum(w'));
disp(['中点是V',num2str(index)]);
end
function dispit(x,flag)
%x：需要显示的矩阵
%flag：为0时表示显示w矩阵，非0时表示显示R矩阵
len=length(x);
s=[];
for j=1:len
if flag==0
s=[s sprintf('%5.2f ',x(j,:))];
else
s=[s sprintf('%d ',x(j,:))];
end
s=[s sprintf(' ')];
end
disp(s);
disp('---------------------------------------------------');
end
% 选择后按Ctrl+t取消注释号%
%
% 示例：
% a=[
% 0,100,100,1.2,9.2,100,0.5;
% 100,0,100,5,100,3.1,2;
% 100,100,0,100,100,4,1.5;
% 1.2,5,100,0,6.7,100,100;
% 9.2,100,100,6.7,0,15.6,100;
% 100,3.1,4,100,15.6,0,100;
% 0.5,2,1.5,100,100,100,0
% ];
%
% b=[
% 0,9.2,1.1,3.5,100,100;
% 1.3,0,4.7,100,7.2,100;
% 2.5,100,0,100,1.8,100;
% 100,100,5.3,0,2.4,7.5;
% 100,6.4,2.2,8.9,0,5.1;
% 7.7,100,2.7,100,2.1,0
% ];
%
% Floyd(a,1,100)
% Floyd(b,1,100) program floyd;
var
st,en,f:integer;
k,n,i,j,x:integer;
a:array[1..10,1..10] of integer;
path:array[1..10,1..10] of integer;
begin
readln(n);
for i:=1 to n do
begin
for j:=1 to n do
begin
read(k);
if k<>0 then
a[i,j]:=k
else
a[i,j]:=maxint;
path[i,j]:=j;
end;
readln;
end;
for x:=1 to n do
for i:=1 to n do
for j:=1 to n do
if a[i,j]>a[i,x]+a[x,j] then
begin
a[i,j]:=a[i,x]+a[x,j];
path[i,j]:=path[i,x];
end;
readln(st,en);
writeln(a[st,en]);
f:=st;
while f<> en do
begin
write(f);
write('-->');
f:=path[f,en];
end;
writeln(en);
end. //以无向图G为入口，得出任意两点之间的路径长度length[i][j]，路径path[i][j][k]，//途中无连接得点距离用0表示，点自身也用0表示publicclassFLOYD{int[][]length=null;//任意两点之间路径长度int[][][]path=null;//任意两点之间的路径publicFLOYD(int[][]G){intMAX=100;introw=G.length;//图G的行数int[][]spot=newint[row][row];//定义任意两点之间经过的点int[]onePath=newint[row];//记录一条路径length=newint[row][row];path=newint[row][row][];for(inti=0;i<row;i++)//处理图两点之间的路径for(intj=0;j<row;j++){if(G[i][j]==0)G[i][j]=MAX;//没有路径的两个点之间的路径为默认最大if(i==j)G[i][j]=0;//本身的路径长度为0}for(inti=0;i<row;i++)//初始化为任意两点之间没有路径for(intj=0;j<row;j++)spot[i][j]=-1;for(inti=0;i<row;i++)//假设任意两点之间的没有路径onePath[i]=-1;for(intv=0;v<row;++v)for(intw=0;w<row;++w)length[v][w]=G[v][w];for(intu=0;u<row;++u)for(intv=0;v<row;++v)for(intw=0;w<row;++w)if(length[v][w]>length[v][u]+length[u][w]){length[v][w]=length[v][u]+length[u][w];//如果存在更短路径则取更短路径spot[v][w]=u;//把经过的点加入}for(inti=0;i<row;i++){//求出所有的路径int[]point=newint[1];for(intj=0;j<row;j++){point[0]=0;onePath[point[0]++]=i;outputPath(spot,i,j,onePath,point);path[i][j]=newint[point[0]];for(ints=0;s<point[0];s++)path[i][j][s]=onePath[s];}}}voidoutputPath(int[][]spot,inti,intj,int[]onePath,int[]point){//输出i//到j//的路径的实际代码，point[]记录一条路径的长度if(i==j)return;if(spot[i][j]==-1)onePath[point[0]++]=j;//System.out.print(+j+);else{outputPath(spot,i,spot[i][j],onePath,point);outputPath(spot,spot[i][j],j,onePath,point);}}publicstaticvoidmain(String[]args){intdata[][]={{0,27,44,17,11,27,42,0,0,0,20,25,21,21,18,27,0},//x1{27,0,31,27,49,0,0,0,0,0,0,0,52,21,41,0,0},//1{44,31,0,19,0,27,32,0,0,0,47,0,0,0,32,0,0},//2{17,27,19,0,14,0,0,0,0,0,30,0,0,0,31,0,0},//3{11,49,0,14,0,13,20,0,0,28,15,0,0,0,15,25,30},//4{27,0,27,0,13,0,9,21,0,26,26,0,0,0,28,29,0},//5{42,0,32,0,20,9,0,13,0,32,0,0,0,0,0,33,0},//6{0,0,0,0,0,21,13,0,19,0,0,0,0,0,0,0,0},//7{0,0,0,0,0,0,0,19,0,11,20,0,0,0,0,33,21},//8{0,0,0,0,28,26,32,0,11,0,10,20,0,0,29,14,13},//9{20,0,47,30,15,26,0,0,20,10,0,18,0,0,14,9,20},//10{25,0,0,0,0,0,0,0,0,20,18,0,23,0,0,14,0},//11{21,52,0,0,0,0,0,0,0,0,0,23,0,27,22,0,0},//12{21,21,0,0,0,0,0,0,0,0,0,0,27,0,0,0,0},//13{18,41,32,31,15,28,0,0,0,29,14,0,22,0,0,11,0},//14{27,0,0,0,25,29,33,0,33,14,9,14,0,0,11,0,9},//15{0,0,0,0,30,0,0,0,21,13,20,0,0,0,0,9,0}//16};for(inti=0;i<data.length;i++)for(intj=i;j<data.length;j++)if(data[i][j]!=data[j][i])return;FLOYDtest=newFLOYD(data);for(inti=0;i<data.length;i++)for(intj=i;j<data[i].length;j++){System.out.println();System.out.print(From+i+to+j+pathis:);for(intk=0;k<test.path[i][j].length;k++)System.out.print(test.path[i][j][k]+);System.out.println();System.out.println(From+i+to+j+length:+test.length[i][j]);}}}

‘伍’ Floyd算法，求高手帮忙修改，能计算小数。输入的权矩阵要能包括小数，现在只能输入整数，跪求！

把第2个和第2个以后的%d改成%f,估计就成了，前面你定义了连个浮点型的二维数组，输入的时候用%d,输入小数后会改成整形的。

‘陆’ Floyd算法的优缺点分析

Floyd算法适用于APSP(All Pairs Shortest Paths，多源最短路径)，是一种动态规划算法，稠密图效果最佳，边权可正可负。此算法简单有效，由于三重循环结构紧凑，对于稠密图，效率要高于执行|V|次Dijkstra算法，也要高于执行V次SPFA算法。
优点：容易理解，可以算出任意两个节点之间的最短距离，代码编写简单。
缺点：时间复杂度比较高，不适合计算大量数据。

‘柒’ matlab floyd 算法注释

A矩阵是邻接矩阵，对角线上为o，其余位置数字表示的是两点之间距离，比如A(1,2)=2,表示从第一个点到第二个点的距离为2.inf是无穷大的意思，这里表示没有直接沟通这两点的路。
n=length(D);设定n为D矩阵的长度。
接下来的两重循环，得到的R矩阵是n*n的矩阵，它每个数据表示的是路径，比如：R(1,3)=1;表示路径为：1-1-3.这里是初始化路径了。
后面的三重循环是floyd算法的关键所在，就是更新路线了。里面的那个判断指的是：
假设有3个点，1
2
3；如果我从1-2-3之间总距离小于1-3的距离，那么我R(1,3)=2；这就是选取更近的路线了。
最后的两个判断是为了不让曾经走过的点再次被遍历。就是不回头的意思了，这个一般都可以忽略了，你照打上去就是了。
不知道这样的解释你是否满意。

‘捌’ floyd-warshall算法的算法概述

单独一条边的路径也不一定是最佳路径。 从任意一条单边路径开始。所有两点之间的距离是边的权的和，(如果两点之间没有边相连, 则为无穷大）。 对于每一对顶点 u 和 v，看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比己知的路径更短。如果是更新它。 不可思议的是，只要按排适当，就能得到结果。// dist(i,j) 为从节点i到节点j的最短距离
For i←1to n do
For j←1to n do
dist(i,j) = weight(i,j)
For k←1to n do// k为“媒介节点”{一定要先枚举媒介节点}
For i←1to n do
For j←1to 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算法）

‘玖’ 用Floyd算法求有向网G中各对顶点之间的最短路径

#define MAX_NAME 5 // 顶点字符串的最大长度+1
#define MAX_INFO 20 // 相关信息字符串的最大长度+1
typedef int VRType;
typedef char VertexType[MAX_NAME];
typedef char InfoType;
#include"c1.h"
#include"c7-1.h"
#include"bo7-1.cpp"
typedef int PathMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef int DistancMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; void ShortestPath_FLOYD(MGraph G,PathMatrix &P,DistancMatrix &D)
{ // 用Floyd算法求有向网G中各对顶点v和w之间的最短路径P[v][w]及其
// 带权长度D[v][w]。若P[v][w][u]为TRUE,则u是从v到w当前求得最短
// 路径上的顶点。
int u,v,w,i;
for(v=0;v<G.vexnum;v++) // 各对结点之间初始已知路径及距离
for(w=0;w<G.vexnum;w++)
{
D[v][w]=G.arcs[v][w].adj;
for(u=0;u<G.vexnum;u++)
P[v][w][u]=FALSE;
if(D[v][w]<INFINITY) // 从v到w有直接路径
{
P[v][w][v]=TRUE;
P[v][w][w]=TRUE;
}
}
for(u=0;u<G.vexnum;u++)
for(v=0;v<G.vexnum;v++)
for(w=0;w<G.vexnum;w++)
if(D[v][u]+D[u][w]<D[v][w]) // 从v经u到w的一条路径更短
{
D[v][w]=D[v][u]+D[u][w];
for(i=0;i<G.vexnum;i++)
P[v][w][i]=P[v][u][i]||P[u][w][i];
}
} void main()
{
MGraph g;
int i,j,k,l,m,n;
PathMatrix p;
DistancMatrix d;
CreateDN(g);
for(i=0;i<g.vexnum;i++)
g.arcs[i][i].adj=0; // ShortestPath_FLOYD()要求对角元素值为0
printf("邻接矩阵:\n");
for(i=0;i<g.vexnum;i++)
{
for(j=0;j<g.vexnum;j++)
printf("%11d",g.arcs[i][j]);
printf("\n");
}
ShortestPath_FLOYD(g,p,d);
printf("d矩阵:\n");
for(i=0;i<g.vexnum;i++)
{
for(j=0;j<g.vexnum;j++)
printf("%6d",d[i][j]);
printf("\n");
}
for(i=0;i<g.vexnum;i++)
for(j=0;j<g.vexnum;j++)
printf("%s到%s的最短距离为%d\n",g.vexs[i],g.vexs[j],d[i][j]);
printf("p矩阵:\n");
l=strlen(g.vexs[0]); // 顶点向量字符串的长度
for(i=0;i<g.vexnum;i++)
{
for(j=0;j<g.vexnum;j++)
{
if(i!=j)
{
m=0; // 占位空格
for(k=0;k<g.vexnum;k++)
if(p[i][j][k]==1)
printf("%s",g.vexs[k]);
else
m++;
for(n=0;n<m*l;n++) // 输出占位空格
printf(" ");
}
else
for(k=0;k<g.vexnum*l;k++) // 输出占位空格
printf(" ");
printf(" "); // 输出矩阵元素之间的间距
}
printf("\n");
}
}

‘拾’ Floyd算法的算法过程

1，从任意一条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大。
2，对于每一对顶点 u 和 v，看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比已知的路径更短。如果是更新它。
把图用邻接矩阵G表示出来，如果从Vi到Vj有路可达，则G[i,j]=d，d表示该路的长度；否则G[i,j]=无穷大。定义一个矩阵D用来记录所插入点的信息，D[i,j]表示从Vi到Vj需要经过的点，初始化D[i,j]=j。把各个顶点插入图中，比较插点后的距离与原来的距离，G[i,j] = min( G[i,j], G[i,k]+G[k,j] )，如果G[i,j]的值变小，则D[i,j]=k。在G中包含有两点之间最短道路的信息，而在D中则包含了最短通路径的信息。
比如，要寻找从V5到V1的路径。根据D，假如D(5,1)=3则说明从V5到V1经过V3，路径为{V5,V3,V1}，如果D(5,3)=3，说明V5与V3直接相连，如果D(3,1)=1，说明V3与V1直接相连。