floyd算法矩阵
⑴ 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]这条路
⑵ 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，构建一个邻接矩阵存储任意两点之间的权值如图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求出距离矩阵D，即以下代码中的矩阵B。
以下matlab程序为从12个点中选出3点，可以此类推。
clear all;
A=[combntns(1:12,3)]; %列出12个居民点选3个缴费点的所有情况。
for i=1:nchoosek(12,3) %for……end， 循环，计算以上列出所有情况下所有居民需要行走的总路程！
A2=A(i,:);
A3=A2(1,1); %读取选取3个居民点
A4=A2(1,2);
A5=A2(1,3);
People=[15 10 12 18 5 24 11 16 13 22 19 20]; %每个居民点的人数的矩阵。
B=[
0 15 37 55 24 60 18 33 48 40 58 67;
15 0 22 40 38 52 33 48 42 55 61 61;
37 22 0 18 16 30 43 28 20 58 39 39;
55 40 18 0 34 12 61 46 24 62 43 34;
24 38 16 34 0 36 27 12 24 49 37 43;
60 52 30 12 36 0 57 42 12 50 31 22;
18 33 43 61 27 57 0 15 45 22 40 61;
33 48 28 46 12 42 15 0 30 37 25 46;
48 42 20 24 24 12 45 30 0 38 19 19;
40 55 58 62 49 50 22 37 38 0 19 40;
58 61 39 43 37 31 40 25 19 19 0 21;
67 61 39 34 43 22 61 46 19 40 21 0 ;
]; %居民到其他居民点所有最短的距离。
B1=B(:,A3); %居民点到所选的缴费点的理论最短距离。
B2=B(:,A4);
B3=B(:,A5);
C=[B1 B2 B3];
D=sort(C,2);
Shortjourney=D(:,1); %每位居民选择缴费点后需要行走的最短路程。
Sum(i)=People*Shortjourney; %所有居民所要行走的路程总和。
end
E=[reshape(Sum,nchoosek(12,3),1)]; %将以上得到的数组转为矩阵。
minposition=find(E==min(E)); %找出最小值在矩阵的位置。
A=[combntns(1:12,3)]; %A的顺序与E的一致！
position=A(minposition,:) %最佳的缴费点的选择。
⑸ 用你熟悉的语言实现Floyd算法，对于具有下面权重矩阵的有向图求解完全最短路径，截图给出运行结果
Floyd的关键是三重循环和松弛式d[i][j] = min(d[i][j], d[i][k] + d[k][j])，代码和注释如下所示：
#include<bits/stdc++.h>
usingnamespacestd;
constintINF=1000000000;
constintn=5;
//邻接矩阵
intd[][n]={
{0,2,INF,1,8},
{6,0,3,2,INF},
{INF,INF,0,4,INF},
{INF,INF,2,0,3},
{3,INF,INF,INF,0}
};
intmain()
{
//floyd
for(intk=0;k<n;++k)
for(inti=0;i<n;++i)
for(intj=0;j<n;++j)
d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
//输出结果
for(inti=0;i<n;++i){
for(intj=0;j<n;++j){
if(j>0)printf("");
if(d[i][j]==INF)printf("INF");
elseprintf("%3d",d[i][j]);
}
puts("");
}
return0;
}
运行结果图：