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

核心思路

算法过程

时间复杂度

优缺点分析

改进和优化

算法实现(Matlab源代码为 pascal语言 java算法)

核心思路

通过一个图的权值矩阵求出它的每两点间的最短路径矩阵。

从图的带权邻接矩阵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，对于每一对顶点 u 和 v，看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比己知的路径更短。如果是更新它。

时间复杂度

O(n^3)

优缺点分析

Floyd算法适用于APSP(All Pairs Shortest Paths)，是一种动态规划算法，稠密图效果最佳，边权可正可负。此算法简单有效，由于三重循环结构紧凑，对于稠密图，效率要高于执行|V|次Dijkstra算法。

优点：容易理解，可以算出任意两个节点之间的最短距离，代码编写简单

缺点：时间复杂度比较高，不适合计算大量数据。

改进和优化

用来计算传递封包。

计算闭包只需将Floyd中的f数组改为布尔数组，将加号改为and就可以了。

算法实现

C语言

#include<stdio.h>

#define MAXV 100

#define INF 32767

#include "graph.h"

//extern void DispMat(MGraph g);

void DispMat(MGraph g)

{

int i,j;

for(i=0;i<g.n;i++)

{

for(j=0;j<g.n;j++)

if(g.edges[i][j]==INF)

printf("%3s","∞");

else

printf("%3d",g.edges[i][j]);

printf("\");

}

}

void ppath(int path[][MAXV],int i,int j)

{

int k;

k=path[i][j];

if(k==-1) return;

ppath(path,i,k);

printf("%d,",k);

ppath(path,k,j);

}

void DisPath(int A[][MAXV],int path[][MAXV],int n)

{

int i,j;

for(i=0;i<n;i++)

for(j=0;j<n;j++)

if(A[i][j]==INF)

{

if(i!=j)

printf("从%d到%d没有路径");

}

else

{

if(i<j)

{

printf("从%d到%d的路径为:",i,j);

printf("%d,",i);

ppath(path,i,j);

printf("%d",j);

printf("\\t路径长度为：%d\",A[i][j]);

}

}

}

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;

}

}

printf("\输出最短路径：\");

DisPath(A,path,n);

}

void main()

{

int i,j,u=0;

MGraph g;

double A[51][51];

for(i=0;i<51;i++)

{

for(j=0;j<51;j++)

{

A[i][j]=INF;

}

}

A[0][18]=2182.0;

A[0][21]=1796.9;

A[0][26]=1392.1;

A[1][3]=1916.3;

A[1][6]=1294.3;

A[1][7]=1968.2;

A[1][8]=2.8638e+003;

A[2][4]=2.2926e+003;

A[2][5]=1.2529e+003;

A[2][20]=7.8233e+003;

A[3][4]=3.5364e+003;

A[3][8]=1.9581e+003;

A[5][15]=5.0045e+003;

A[7][10]=2.0594e+003;

A[7][18]=5.9179e+003;

A[8][12]=1.7568e+003;

A[9][10]=1.9455e+003;

A[9][14]=2.6813e+003;

A[10][18]=5.9095e+003;

A[11][12]=1.4177e+003;

A[11][13]=1.6696e+003;

A[12][13]=1.4568e+003;

A[12][15]=4.8058e+003;

A[12][25]=5.7566e+003;

A[13][18]=3.1135e+003;

A[13][19]=3.4557e+003;

A[14][16]=2.6077e+003;

A[14][17]=2.1957e+003;

A[14][18]=5.3422e+003;

A[14][21]=3.2967e+003;

A[15][22]=2.8610e+003;

A[15][25]=4.2354e+003;

A[16][23]=2.0976e+003;

A[17][21]=1.8239e+003;

A[17][23]=1.7745e+003;

A[18][31]=2.1037e+003;

A[19][24]=2.2586e+003;

A[19][25]=1.9662e+003;

A[20][22]=1.4989e+003;

A[21][26]=2.1917e+003;

A[21][36]=2.8802e+003;

A[22][29]=1.0979e+003;

A[22][30]=1.2875e+003;

A[23][32]=1.3119e+003;

A[24][31]=1.7801e+003;

A[25][29]=1.8859e+003;

A[25][41]=4.1546e+003;

A[26][31]=1.5370e+003;

A[27][31]=1.0678e+003;

A[27][36]=2.2039e+003;

A[27][39]=1.7799e+003;

A[28][30]=1.0179e+003;

A[28][33]=1.3257e+003;

A[30][41]=4.9976e+003;

A[31][34]=2.3247e+003;

A[32][35]=1.1140e+003;

A[33][46]=3.7585e+003;

A[34][40]=1.6308e+003;

A[35][38]=1.4097e+003;

A[36][38]=1.5374e+003;

A[36][45]=3.1825e+003;

A[37][40]=2.0901e+003;

A[37][41]=2.6019e+003;

A[38][43]=2.6184e+003;

A[40][45]=3.2170e+003;

A[40][47]=2.3312e+003;

A[40][50]=3.0435e+003;

A[41][44]=2.3660e+003;

A[41][46]=2.7354e+003;

A[42][43]=917.6737;

A[42][45]=2.3517e+003;

A[42][49]=1.9714e+003;

A[44][48]=2.1525e+003;

A[44][50]=4.9870e+003;

A[45][50]=3.1028e+003;

A[46][48]=1.4941e+003;

A[49][50]=3.5688e+003;

for(i=0;i<51;i++)

{

for(j=0;j<51;j++)

{

if(A[i][j]!=0)

A[j][i]=A[i][j];

}

}

g.n=51;

g.e=154;

for(i=0;i<g.n;i++)

for(j=0;j<g.n;j++)

g.edges[i][j]=A[i][j];

printf("\");

printf("图G的邻接矩阵：\");

DispMat(g);

Floyd(g);

printf("\");

}

C++语言

#include<fstream>

#define Maxm 501

using namespace std;

ifstream fin;

ofstream fout("APSP.out");

int p,q,k,m;

int Vertex,Line[Maxm];

int Path[Maxm][Maxm],Dist[Maxm][Maxm];

void Root(int p,int q)

{

if (Path[p][q]>0)

{

Root(p,Path[p][q]);

Root(Path[p][q],q);

}

else

{

Line[k]=q;

k++;

}

}

int main()

{

memset(Path,0,sizeof(Path));

memset(Dist,0,sizeof(Dist));

fin >> Vertex;

for(p=1;p<=Vertex;p++)

for(q=1;q<=Vertex;q++)

fin >> Dist[p][q];

for(k=1;k<=Vertex;k++)

for(p=1;p<=Vertex;p++)

if (Dist[p][k]>0)

for(q=1;q<=Vertex;q++)

if (Dist[k][q]>0)

{

if (((Dist[p][q]>Dist[p][k]+Dist[k][q])||(Dist[p][q]==0))&&(p!=q))

{

Dist[p][q]=Dist[p][k]+Dist[k][q];

Path[p][q]=k;

}

}

for(p=1;p<=Vertex;p++)

{

for(q=p+1;q<=Vertex;q++)

{

fout << "\==========================\";

fout << "Source:" << p << '\' << "Target " << q << '\';

fout << "Distance:" << Dist[p][q] << '\';

fout << "Path:" << p;

k=2;

Root(p,q);

for(m=2;m<=k-1;m++)

fout << "-->" << Line[m];

fout << '\';

fout << "==========================\";

}

}

fin.close();

fout.close();

return 0;

}

注解：无法连通的两个点之间距离为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 50 00

Sample Output

==========================

Source: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

Distance: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)

%x为此图的距离矩阵

%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('\')];

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.

java算法

package third;

//以无向图G为入口，得出任意两点之间的路径长度length[i][j]，路径path[i][j][k]，

//途中无连接得点距离用0表示，点自身也用0表示

public class FLOYD {

int[][] length = null;// 任意两点之间路径长度

int[][][] path = null;// 任意两点之间的路径

public FLOYD(int[][] G) {

int MAX = 100;

int row = G.length;// 图G的行数

int[][] spot = new int[row][row];// 定义任意两点之间经过的点

int[] onePath = new int[row];// 记录一条路径

length = new int[row][row];

path = new int[row][row][];

for (int i = 0; i < row; i++)

// 处理图两点之间的路径

for (int j = 0; j < row; j++) {

if (G[i][j] == 0)

G[i][j] = MAX;// 没有路径的两个点之间的路径为默认最大

if (i == j)

G[i][j] = 0;// 本身的路径长度为0

}

for (int i = 0; i < row; i++)

// 初始化为任意两点之间没有路径

for (int j = 0; j < row; j++)

spot[i][j] = -1;

for (int i = 0; i < row; i++)

// 假设任意两点之间的没有路径

onePath[i] = -1;

for (int v = 0; v < row; ++v)

for (int w = 0; w < row; ++w)

length[v][w] = G[v][w];

for (int u = 0; u < row; ++u)

for (int v = 0; v < row; ++v)

for (int w = 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 (int i = 0; i < row; i++) {

// 求出所有的路径

int[] point = new int[1];

for (int j = 0; j < row; j++) {

point[0] = 0;

onePath[point[0]++] = i;

outputPath(spot, i, j, onePath, point);

path[i][j] = new int[point[0]];

for (int s = 0; s < point[0]; s++)

path[i][j][s] = onePath[s];

}

}

}

void outputPath(int[][] spot, int i, int j, 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);

}

}

public static void main(String[] args) {

int data[][] = {

{ 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 (int i = 0; i < data.length; i++)

for (int j = i; j < data.length; j++)

if (data[i][j] != data[j][i])

return;

FLOYD test=new FLOYD(data);

for (int i = 0; i < data.length; i++)

for (int j = i; j < data[i].length; j++) {

System.out.println();

System.out.print("From " + i + " to " + j + " path is: ");

for (int k = 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]);

}

}

}