来自当知百科
跳转到: 导航搜索

目录

核心思路

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

  从图的带权邻接矩阵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]这条路

算法过程

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

时间复杂度

  O(n^3)

优缺点分析

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

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

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

算法实现

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],Map[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(Map,0,sizeof(Map));

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

  fin >> Vertex;

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

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

  {

  fin >> Map[p][q];

  Dist[p][q]=Map[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 << "\n==========================\n";

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

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

  fout << "Path:" << p;

  k=2;

  Root(p,q);

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

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

  fout << '\n';

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

  }

  }

  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源代码为

  %floyd算法通用程序,输入a为赋权邻接矩阵

  %输出为距离矩阵D,和最短路径矩阵path

  function [D,path]=floyd(a)

  n=size(a,1);

  D=a;

  path=zeros(n,n);

  for i=1:n

  for j=1:n

  if D(i,j)~=inf

  path(i,j)=j;

  end

  end

  end

  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

  %配合floyd算法的后续程序,s为源点,t为宿点

  %L为长度,R为路由

  function [L,R]=router(D,path,s,t)

  L=zeros(0,0);

  R=s;

  while 1

  if s==t

  L=fliplr(L);

  L=[0,L];

  L=L(end);

  return

  end

  L=[L,D(s,t)];

  R=[R,path(s,t)];

  s=path(s,t);

  if s==0

  return

  end

  end 

  在M文件中建立

pascal语言:

  program floyd;

  var

  st,en,f:integer;

  k,n,i,j,x:integer;

  a:array[1..10,1..10]of integer;

  path,map1,map2: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]);

  writeln;

  f:=st;

  while f<> en do

  begin

  write(f);

  write('-->');

  f:=path[f,en];

  end;

  write(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]);

  }

  }

  }

个人工具
名字空间

变换
查看
操作
导航
工具箱