Floyd来自算法又称为插点法，是一种用于寻找给定的加权图中多源点之间最短路下离规尔径的算法。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛360百科伊德命名。
- 中文名 弗洛伊德算法
- 外文名 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来记录两点间的最短路径。
采用松弛技术(360百科松弛操作)，对在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]这条路。
算法过程
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则说明从V怀训5到V1经过V3，路径为{V5,V3,V1}，如果D(5,3)=3，说明V5与V3直接相连，如果D(3,1)=1，说明V3与V1直接相连。
复杂度类型
客律垂右云冷爱妈看 时间复杂度:O(n^3);
空间复杂度:来自O(n^2)
优缺点分析
Floyd算法适用于皇了抓年最APSP(All Pairs Shortest Paths，多源最短路径)，是一种动态规划算法，稠密图效果最佳，边权可正可负。此算法简单有效，由于三重循环结构于究南职宁友染已音话角紧凑，对于稠密图，效率要高于360百科执行|V|次Dijks斗tra算法，也要高于执行V次SPFA算法。
优点:耐自容呼物杂往容易理解，可以算出任意两个结节点之间的最短距离，代码封编写简单。
缺点:时间复杂度比较高，不适合计算大量数据。
算法描述
a) 初始化:D们语喜升[u,v]=A[u,v]
b) For k:=1 to n
For i:=1 to n
For j:=1 to n
If D[i,j]>D[i,k]+D[k,j] Then
D[i,j]:=D[i,k]+D[k,j];
c) 算法结束:D即为所有点对的最短路径矩阵
参考代码
注解:无法连通的两个点之间距离为0;
Sample Input
7
0行呼完式用下今静德0 20 50 30 00 00 00
特突怀外欢封同善感李才 20 00 25 00 00 70 00
50 25 00 40 25 50 00
30 00 40 00 55 00 00
00 00 25 55 00 10 70
00 70 50 00 10 00 50
00 00 00 0坐0 70 5000
Sample Output
==========================
So危什九阿拿读海类半urce:1
Target 2
Distance:20
Path:1-群胡女探屋可湖->2
==========================
==========================
Source:1
Target 3
Distance:45
Path:1-->2-->3
=====================厚亮祖督跑滑同植别源赵=====
=======失皮输议科跑审手希通===================
Source:1
Target 4
Distance:30
Path:1-->4
==========================
============扬呢秋欢础吧==============
Source:1
Target 5
Dis排供刘跳tance:70
Path:1-->2-->3-->5
==========================
==修延抓花定片赵额引夜========================
Source:1
Target 6
Distance:80
Path:1-->2-->3-->5-->6
==========================
==========================
Source:1
Target 7
Distance:130
Path:1-->2-->3-->5-->6-->7
==========================
==========================
Source:2
Target 3
Distance:25
Path:2-->3
==========================
==========================
Source:2
Target 4
Distance:50
Path:2-->1-->4
==========================
==========================
Source:2
Target 5
Distance:50
Path:2-->3-->5
==========================
==========================
Source:2
Target 6
Distance:60
Path:2-->3-->5-->6
==========================
==========================
Source:2
Target 7
Distance:110
Path:2-->3-->5-->6-->7
==========================
==========================
Source:3
Target 4
Distance:40
Path:3-->4
==========================
==========================
Source:3
Target 5
Distance:25
Path:3-->5
==========================
==========================
Source:3
Target 6
Distance:35
Path:3-->5-->6
==========================
==========================
Source:3
Target 7
Distance:85
Path:3-->5-->6-->7
==========================
==========================
Source:4
Target 5
Distance:55
Path:4-->5
==========================
==========================
Source:4
Target 6
Distance:65
Path:4-->5-->6
==========================
==========================
Source:4
Target 7
Distance:115
Path:4-->5-->6-->7
==========================
==========================
Source:5
Target 6
Distance:10
Path:5-->6
==========================
==========================
Source:5
Target 7
Distance:60
Path:5-->6-->7
==========================
==========================
Source:6
Target 7
Distance:50
Path:6-->7
Matlab源代码
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\t',x(j,:))];
else
s=[s sprintf('%d\t',x(j,:))];
end
s=[s sprintf('\n')];
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)
pascal语言
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.
评论留言