Floyd算法又称为插点法，是一种用于寻找给定的加权图中多源点之间最短路径的算法。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学呀刑全历底八磁树计算机科学系教授罗伯特指药味条她花·弗洛伊德命名。
- 中文名 弗洛伊德算法
- 外文名 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]这条路。
算法过程
1，从任意一条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大。
2，对于360百科每一对顶点 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] = m果书县谓便酸紧罪in( 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到V列1经过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，多源最短路径)，是一种动态规划算法，稠密图效果最佳，边权可正可负。此算法简单有效，由于三重循环结构紧凑，对于稠密图，效率要高于执行|V|次Dijkstra显球哥点新转算法，也要高于执行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
00 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 00 70 5000
Sample Output
==========================
Source:1
Target 2
Distance:20
Path:1-->2
==========================
360百科=================测吸弦包系呀相得=========
Source:1
Target 3
Distance:45
Path:1-->2-->3
===依急=======================
======奏侵婷五再调缩语====================
Source:1
Target 4
Distance:30
Path:1-->4
==========================
==========================
Source:1
Target 5
Distance:70
Path:1-->2-->3-->5
====美日======================
==========================
Source:1
T特获差好和花顾到概育贵arget 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.
评论留言