Floyd最短路径算法

Floyd最短路径算法

Posted on 2009-07-10 16:26 YDN 阅读(375) 评论(0)  编辑 收藏 网摘 所属分类: 树和图

      在图论中经常会遇到这样的问题，在一个有向图里，求出任意两个节点之间的最短距离。当节点之间的权值是正值的时候，我们可以采用Dijkstra算法，用贪心策略加于解决。但当节点之间的权值有负数的时候，Dijkstra就行不通了，这里介绍另外一种算法——Floyd最短路径算法。
问题描述：
      如果有一个矩阵D=[d(ij)]，其中d(ij)>0表示i城市到j城市的距离。若i与j之间无路可通，那么d(ij)就是无穷大。又有d(ii)=0。编写一个程序，通过这个距离矩阵D，把任意两个城市之间的最短路径找出来。

【分析】
       如何找出最短路径呢，这里需要用到动态规划的思想，对于任何一个城市而言，i 到 j 的最短距离不外乎存在经过 i 与 j 之间的k和不经过k两种可能，所以可以令k=1，2，3，...，n(n是城市的数目)，再检查d(ij)与d(ik)+d(kj)的值；在此d(ik)与d(kj)分别是目前为止所知道的 i 到 k 与 k 到 j 的最短距离，因此d(ik)+d(kj)就是 i 到 j 经过k的最短距离。所以，若有d(ij)>d(ik)+d(kj)，就表示从 i 出发经过 k 再到j的距离要比原来的 i 到 j 距离短，自然把i到j的d(ij)重写为d(ik)+d(kj)<这里就是动态规划中的决策>，每当一个k查完了，d(ij)就是目前的 i 到 j 的最短距离。重复这一过程，最后当查完所有的k时，d(ij)里面存放的就是 i 到 j 之间的最短距离了<这就是动态规划中的记忆化搜索>。利用一个三重循环产生一个存储每个结点最短距离的矩阵.      
      用三个for循环把问题解决了，但是有一个问题需要注意，那就是for循环的嵌套的顺序：我们可能随手就会写出这样的枚举程序，但是仔细考虑的话，会发现是有问题的：
for i:=1 to n do
      for j:=1 to n do
            for k:=1 to n do
                   if.....
      问题出在我们太早的把i-k-j的距离确定下来了，假设一旦找到了i-p-j最短的距离后，i到j就相当处理完了，以后不会在改变了，一旦以后有使i到j的更短的距离时也不能再去更新了，所以结果一定是不对的。所以应当象下面一样来写程序：
for k:=1 to n do
      for i:=1 to n do
            for j:=1 to n do
                  if .....
      这样作的意义在于固定了k，把所有i到j而经过k的距离找出来，然后象开头所提到的那样进行比较和重写，因为k是在最外层的，所以会把所有的i到j都处理完后，才会移动到下一个K。

 【Floyd算法实例】
现有一张城市地图，图中的顶点为城市，无向边代表两个城市间的连通关系，边上的权代表城市之间的距离。求每个城市的最短距离
【输入】 第一行两个数v,e，分别代表城市数和边数 以下e行，每行为两个顶点和它们之间的边权。
【输出】 所有可能连接的城市的最短距离。
　 【输入样例】
6 10
1 2 10
1 5 19
1 6 21
2 3 5
2 4 6
2 6 11
3 4 6
4 5 18
4 6 14
5 6 33
　
【输出样例】
1 2 10
1 3 15
1 4 16
1 5 19
1 6 21
2 3 5
2 4 6
2 5 24
2 6 11
3 4 6
3 5 24
3 6 16
4 5 18
4 6 14
5 6 32

Code
 1program floyd_example;
 2const
 3  maxn=10;
 4var
 5  n,s,t,i,j:integer;
 6  dist:array[1..maxn,1..maxn] of real;
 7  prev:array[1..maxn,1..maxn] of 0..maxn;
 8procedure init;
 9  var
10    m,i,u,v:integer;
11  begin
12    assign(input,'floyd.in');
13    reset(input);
14    assign(output,'floyd.out');
15    rewrite(output);
16    readln(n,m);
17    fillchar(prev,sizeof(prev),0);
18    for u:=1 to n do
19     for v:=1 to n do
20       dist[u,v]:=1e10;
21    for i:=1 to m do
22      begin
23        readln(u,v,dist[u,v]);
24        dist[v,u]:=dist[u,v];
25        prev[u,v]:=u;
26        prev[v,u]:=v;
27     end;
28  end;{init}
29procedure floyd;
30  var
31    i,j,k:integer;
32  begin
33    for k:=1 to n do
34      for i:=1 to n do
35         for j:=1 to n do
36           if (dist[i,k]+dist[k,j]<dist[i,j]) 
37              then  begin
38                 dist[i,j]:=dist[i,k]+dist[k,j];
39                 prev[i,j]:=prev[k,j];
40                end;
41  end;{floyd}
42procedure print(i,j:integer);
43  begin
44    if i=j
45      then write(i)
46      else if prev[i,j]=0
47             then write('No Solution!')
48             else begin
49                  print(i,prev[i,j]);
50                  write('->',j);
51                  end;
52  end;{print}
53begin
54  init;
55  floyd;
56  for i:=1 to n do
57    for j:=i+1 to n do
58      begin
59        write(i,' ',j,' ');
60        write(dist[i,j]:0:0,' ');
61        print(i,j);
62        writeln;
63      end;
64  close(input);
65  close(output);
66end.