弗洛伊德算法矩阵

‘壹’ 每一对顶点之间的最短路径是什么

每一对顶点之间的最短路径是指对于给定的带权有向图G＝（v，E），要对G中任意一对顶点有序对（vi，vj）（vi≠vj），找出vi到vj的最短距离和vj到vi的最短距离。

解决此问题的一个有效方法是：轮流以每一个顶点为源点，重复执行Dijkstra算法n次，即可求得有向图G＝（v，E）中每一对顶点间的最短路径，总的时间复杂度为0（n2）。

弗洛伊德（Floyd）提出了另一个求任意两顶点之间最短路径的算法，虽然其时间复杂度也是0（n2），但算法形式更为简明，易于理解与编程。

1.弗洛伊德算法的思想弗洛伊德算法是从图的邻接矩阵开始，按照顶点v0，v1，v2，v2，…，vn的次序，分别以每个顶点vk（0≤k＜n）作为新考虑的中间点，在第k－1次运算D（k－1）的基础上，求出每一对顶点之间vi到vj的最短路径长度D（k）［i］［j］，计算公式为：

D（k）［i］［j］＝min｛D（k－1）［i］［j］，D（k－1）［i］［k］＋D（k－1）［k］［j］｝重复执行n次后，D（k）［i］［j］中保留的值就是每对顶点的vi到vj的最短路径长度。

2.弗洛伊德算法的步骤（1）从图的带权邻接矩阵G．arcs［］［］开始，即D（－1）＝arcs［］［］，每次以上一次D（k－1）为基础，用公式D（k）［i］［j］＝min｛D（k－1）［i］［j］，D（k－1）［i］［k］＋D（k－1）［k］［j］｝计算出D（k）［i］［j］的值，即D（k－1）［i］［k］＋D（k－1）［k］［j］＜D（k－1）［i］［j］才修改，若D（k）［i］［j］修改过，则相应的路径P（k）［i］［j］也要作相应的修改，即P（k）［i］［j］＝P（k－1）［i］［k］＋P（k－1）［k］［j］。

（2）重复上述过程n次后，D（k）［i］［j］中保存的就是每一对顶点的最短路径长度，P（k）［i］［j］中保存的就是每一对顶点的最短路径。

说明：从计算公式可以看出，i＝j是对角线上的元素；i＝k是i行上的元素；j＝k是j列上的元素，这些特殊的顶点不用计算，保留原来的数据值。因此，计算的数据元素减少了很多。

‘贰’ floyd算法 是动态规划的思想吗

1.定义概览
Floyd-Warshall算法（Floyd-Warshall
algorithm）是解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权的最短路径问题，同时也被用于计算有向图的传递闭包。Floyd-Warshall算法的时间复杂度为O(N3)，空间复杂度为O(N2)。
2.算法描述
1)算法思想原理：
Floyd算法是一个经典的动态规划算法。用通俗的语言来描述的话，首先我们的目标是寻找从点i到点j的最短路径。从动态规划的角度看问题，我们需要为这个目标重新做一个诠释（这个诠释正是动态规划最富创造力的精华所在）
从任意节点i到任意节点j的最短路径不外乎2种可能，1是直接从i到j，2是从i经过若干个节点k到j。所以，我们假设Dis(i,j)为节点u到节点v的最短路径的距离，对于每一个节点k，我们检查Dis(i,k)
+
Dis(k,j)
<
Dis(i,j)是否成立，如果成立，证明从i到k再到j的路径比i直接到j的路径短，我们便设置Dis(i,j)
=
Dis(i,k)
+
Dis(k,j)，这样一来，当我们遍历完所有节点k，Dis(i,j)中记录的便是i到j的最短路径的距离。
2).算法描述：
a.从任意一条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大。

b.对于每一对顶...
1.定义概览
Floyd-Warshall算法（Floyd-Warshall
algorithm）是解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权的最短路径问题，同时也被用于计算有向图的传递闭包。Floyd-Warshall算法的时间复杂度为O(N3)，空间复杂度为O(N2)。
2.算法描述
1)算法思想原理：
Floyd算法是一个经典的动态规划算法。用通俗的语言来描述的话，首先我们的目标是寻找从点i到点j的最短路径。从动态规划的角度看问题，我们需要为这个目标重新做一个诠释（这个诠释正是动态规划最富创造力的精华所在）
从任意节点i到任意节点j的最短路径不外乎2种可能，1是直接从i到j，2是从i经过若干个节点k到j。所以，我们假设Dis(i,j)为节点u到节点v的最短路径的距离，对于每一个节点k，我们检查Dis(i,k)
+
Dis(k,j)
<
Dis(i,j)是否成立，如果成立，证明从i到k再到j的路径比i直接到j的路径短，我们便设置Dis(i,j)
=
Dis(i,k)
+
Dis(k,j)，这样一来，当我们遍历完所有节点k，Dis(i,j)中记录的便是i到j的最短路径的距离。
2).算法描述：
a.从任意一条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大。

b.对于每一对顶点
u
和
v，看看是否存在一个顶点
w
使得从
u
到
w
再到
v
比己知的路径更短。如果是更新它。
3).Floyd算法过程矩阵的计算----十字交叉法
方法：两条线，从左上角开始计算一直到右下角
如下所示
给出矩阵，其中矩阵A是邻接矩阵，而矩阵Path记录u,v两点之间最短路径所必须经过的点

‘叁’ 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直接相连。

‘肆’ floyd算法计算最短距离时，赋权邻接矩阵怎么算

Model:
!2个工厂，3个中转站及4个客户的运输问题;
sets:
plant/A,B/:proce;
warhouse/x,y,z/;
costomer/1..4/:require;
link(plant, warhouse,costomer):poss,cost,x;
endsets
data:
proce=9,8;
require=3,4,3,5;
!邻接矩阵;
poss = 1 1 0 0 !A-x-1,A-x-2,A-x-3,A-x-4;
1 1 1 0 !A-y-1,A-y-2,A-y-3,A-y-4;
0 0 0 0 !A-z-1,A-z-2,A-z-3,A-z-4;
0 1 0 0 !B-x-1,B-x-2,B-x-3,B-x-4;
1 1 1 0 !B-y-1,B-y-2,B-y-3,B-y-4;
0 1 1 1; !B-z-1,B-z-2,B-z-3,B-z-4;
!赋权矩阵;
cost=6 8 0 0
11 8 9 0
0 0 0 0
8 10 0 0
10 7 8 0
0 10 9 6;
enddata
!目标函数;
min=@sum(link:poss*cost*x);
!约束条件;
@for(plant(i):@sum(warhouse(j): @sum(costomer(k):poss(i,j,k)*x(i,j,k)))<proce(i));
!对于厂家I，运出的从”I-J-K”的运量不超过该厂的产量;
@for(costomer(k) :@sum(plant(i):@sum(warhouse(j): poss(i,j,k)*x(i,j,k)))=require(k));
! 对于客户K，运入的从”I-J-K”的运量不超过该客户的需求量;
end
①邻接矩阵，两个厂家，则分两组；3个中转站，则每组3行；即共有2*3=6行；
第一组指的是从“厂家A”运出的，第二组指的是从“厂家B”运出的．
第一行表示通过中转站X，第二行表示通过中转站Y，第三行表示通过中转站Z；
第一列表示到达客户1，第二列表示到达客户2，第三列表示到达客户3，第4列表示到达客户4．
如poss24属于第一组的第2行第4列的元素，则表示从A-y-4的运输情况．
②赋权矩阵，指的是相应的线路对应的权重和(运费之和).

‘伍’ Floyd算法中的矩阵就是邻接矩阵么

是的。邻接矩阵。存储联通状态的。

‘陆’ floyd如何判断有多条最短路径

1.定义概览
Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。注意该算法要求图中不存在负权边。
问题描述：在无向图 G=(V,E) 中，假设每条边 E[i] 的长度为 w[i]，找到由顶点 V0 到其余各点的最短路径。（单源最短路径）

2.算法描述
1)算法思想：设G=(V,E)是一个带权有向图，把图中顶点集合V分成两组，第一组为已求出最短路径的顶点集合（用S表示，初始时S中只有一个源点，以后每求得一条最短路径 , 就将加入到集合S中，直到全部顶点都加入到S中，算法就结束了），第二组为其余未确定最短路径的顶点集合（用U表示），按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S中的顶点的距离就是从v到此顶点的最短路径长度，U中的顶点的距离，是从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。
2)算法步骤：
a.初始时，S只包含源点，即S＝{v}，v的距离为0。U包含除v外的其他顶点，即:U={其余顶点}，若v与U中顶点u有边，则<u,v>正常有权值，若u不是v的出边邻接点，则<u,v>权值为∞。
b.从U中选取一个距离v最小的顶点k，把k，加入S中（该选定的距离就是v到k的最短路径长度）。
c.以k为新考虑的中间点，修改U中各顶点的距离；若从源点v到顶点u的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点u的距离值，修改后的距离值的顶点k的距离加上边上的权。
d.重复步骤b和c直到所有顶点都包含在S中。

执行动画过程如下图

3.算法代码实现：

const int MAXINT = 32767;
const int MAXNUM = 10;
int dist[MAXNUM];
int prev[MAXNUM];

int A[MAXUNM][MAXNUM];

void Dijkstra(int v0)
{
bool S[MAXNUM]; // 判断是否已存入该点到S集合中
int n=MAXNUM;
for(int i=1; i<=n; ++i)
{
dist[i] = A[v0][i];
S[i] = false; // 初始都未用过该点
if(dist[i] == MAXINT)
prev[i] = -1;
else
prev[i] = v0;
}
dist[v0] = 0;
S[v0] = true;
for(int i=2; i<=n; i++)
{
int mindist = MAXINT;
int u = v0; // 找出当前未使用的点j的dist[j]最小值
for(int j=1; j<=n; ++j)
if((!S[j]) && dist[j]<mindist)
{
u = j; // u保存当前邻接点中距离最小的点的号码
mindist = dist[j];
}
S[u] = true;
for(int j=1; j<=n; j++)
if((!S[j]) && A[u][j]<MAXINT)
{
if(dist[u] + A[u][j] < dist[j]) //在通过新加入的u点路径找到离v0点更短的路径
{
dist[j] = dist[u] + A[u][j]; //更新dist
prev[j] = u; //记录前驱顶点
}
}
}
}

4.算法实例
先给出一个无向图

用Dijkstra算法找出以A为起点的单源最短路径步骤如下

Floyd算法
1.定义概览
Floyd-Warshall算法（Floyd-Warshall algorithm）是解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权的最短路径问题，同时也被用于计算有向图的传递闭包。Floyd-Warshall算法的时间复杂度为O(N3)，空间复杂度为O(N2)。

2.算法描述
1)算法思想原理：
Floyd算法是一个经典的动态规划算法。用通俗的语言来描述的话，首先我们的目标是寻找从点i到点j的最短路径。从动态规划的角度看问题，我们需要为这个目标重新做一个诠释（这个诠释正是动态规划最富创造力的精华所在）
从任意节点i到任意节点j的最短路径不外乎2种可能，1是直接从i到j，2是从i经过若干个节点k到j。所以，我们假设Dis(i,j)为节点u到节点v的最短路径的距离，对于每一个节点k，我们检查Dis(i,k) + Dis(k,j) < Dis(i,j)是否成立，如果成立，证明从i到k再到j的路径比i直接到j的路径短，我们便设置Dis(i,j) = Dis(i,k) + Dis(k,j)，这样一来，当我们遍历完所有节点k，Dis(i,j)中记录的便是i到j的最短路径的距离。
2).算法描述：
a.从任意一条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大。
b.对于每一对顶点 u 和 v，看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比己知的路径更短。如果是更新它。
3).Floyd算法过程矩阵的计算----十字交叉法
方法：两条线，从左上角开始计算一直到右下角 如下所示
给出矩阵，其中矩阵A是邻接矩阵，而矩阵Path记录u,v两点之间最短路径所必须经过的点

相应计算方法如下：

最后A3即为所求结果

3.算法代码实现

typedef struct
{
char vertex[VertexNum]; //顶点表
int edges[VertexNum][VertexNum]; //邻接矩阵,可看做边表
int n,e; //图中当前的顶点数和边数
}MGraph;

void Floyd(MGraph g)
{
int A[MAXV][MAXV];
int path[MAXV][MAXV];
int i,j,k,n=g.n;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
A[i][j]=g.edges[i][j];
path[i][j]=-1;
}
for(k=0;k<n;k++)
{
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(A[i][j]>(A[i][k]+A[k][j]))
{
A[i][j]=A[i][k]+A[k][j];
path[i][j]=k;
}
}
}

‘柒’ 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算法思想：1，构建一个邻接矩阵存储任意两点之间的权值如图D0.

2、例如求v1,v4之间的最短路径。先增加v2做中间顶点，D[1][4]=∞。if（D[1][4]>D[1][2]+D[2]4]）=6+4）D[1][4]=10;这样就可以了。

3、如不能在离得较远的两点(例v1,v9）直接得到上述可以满足if的中间点，则跟据你书本的代码可以先构建原点到中间点的最短路径，继而就可以求得vi,v9之间的最短路径

‘玖’ floyd算法能不能保证有最优解

Floyd算法又称为弗洛伊德算法，插点法，是一种用于寻找给定的加权图中顶点间最短路径的算法。

算法过程:

把图用邻接距阵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直接相连。

‘拾’ 利用FLOYD求出的path矩阵怎么看

这是一个我写的Floyd算法的程序。w是图的邻接矩阵需要事先输入并保存在工作空间中，调用方法为：[D,path]=floyd(w)。给出的结果D为路径的邻接矩阵，path为路径所经过的端点顺序。

程序为：
<pre t="code" l="cpp">function [D,path]=floyd(w)
%D R a
n=size(w,1);
%设初值
D=w;
path=zeros(n);
for i=1:n
for j=1:n
if D(i,j)~=inf
path(i,j)=j;
end
end
end
%迭代，更新D path
for k=1:n
for i=1:n
for j=1:n
if D(i,k)+D(k,j)<D(i,j)
D(i,j)=D(i,k)+D(k,j);
path(i,j)=path(i,k);
end
end
end
end