Go语言视频零基础入门到精通

javalearner

Floyd-Warshall算法（Floyd-Warshall algorithm）是解决任意两点间的最短路径的一种算法，可以正确处理带权有向图或负权的最短路径问题      解决此问题有两种方法：
其一是分别以图中每个顶点为源点共调用n次算法；
其二是采用Floyd算法。

    两种算法的时间复杂度均为O(n3)，但后者形式上比较简单。

Floyd算法的基本思想：
  （1）利用二维数组dist[j]记录当前vi到vj的最短路径长度，数组dist的初值等于图的带权邻接矩阵;

（2）集合S记录当前允许的中间顶点，初值S=Φ;
   
  
   
   

     
   

     
   
  
  （3）依次向S中加入v0 ,v1… vn-1，每加入一个顶点，对dist[j]进行一次修正：设S={v0 ,v1… vk-1}，加入vk，则dist(k)[j] = min{ dist(k-1)[j]，dist(k-1)[k]+dist(k-1)[k][j]}。
dist(k)[j]的含义：允许中间顶点的序号最大为k时从vi到vj的最短路径长度。   dist(n-1)[j]就是vi到vj的最短路径长度。  

1. import java.util.ArrayList;   
   
2. import java.util.List;   
   
3.   
   
4.   
   
5. public class FloydInGraph {   
   
6.   
   
7.     private static int INF=Integer.MAX_VALUE;   
   
8.          //dist[i][j]=INF<==>i 和 j之间没有边   
   
9.     private int[][] dist;   
   
10.          //顶点i 到 j的最短路径长度，初值是i到j的边的权重     
    
11.     private int[][] path;     
    
12.     private List< Integer> result=new ArrayList< Integer>();   
    
13.       
    
14.     public static void main(String[] args) {   
    
15.         FloydInGraph graph=new FloydInGraph(5);   
    
16.         int[][] matrix={   
    
17.                 {INF,30,INF,10,50},   
    
18.                 {INF,INF,60,INF,INF},   
    
19.                 {INF,INF,INF,INF,INF},   
    
20.                 {INF,INF,INF,INF,30},   
    
21.                 {50,INF,40,INF,INF},   
    
22.         };   
    
23.                 /* 最下面的图
    
24.                 int[][] matrix = {
    
25.     {0 ,20,INF,INF,20,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF},
    
26.     {20,0 ,30,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF},
    
27.     {INF,30,0 ,20,INF,30,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF},
    
28.     {INF,INF,20,0 ,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF},
    
29.     {20,INF,INF,INF,0 ,10,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF},
    
30.     {INF,INF,30,INF,10,0 ,20,50,INF,INF,INF,INF,INF,INF,INF,INF,INF},
    
31.     {INF,INF,INF,INF,INF,20,0 ,40,10,INF,INF,INF,INF,INF,INF,INF,INF},
    
32.     {INF,INF,INF,INF,INF,50,40,0 ,INF,20,20,INF,INF,INF,INF,INF,INF},
    
33.     {INF,INF,INF,INF,INF,INF,10,INF,0 ,20,INF,INF,INF,30,INF,INF,INF},
    
34.     {INF,INF,INF,INF,INF,INF,INF,20,20,0 ,20,INF,INF,INF,INF,INF,INF},
    
35.     {INF,INF,INF,INF,INF,INF,INF,20,INF,20,0 ,20,INF,INF,INF,INF,INF},
    
36.     {INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,20,0 ,10,INF,INF,INF,INF},
    
37.     {INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,10,0 ,INF,INF,20,INF},
    
38.     {INF,INF,INF,INF,INF,INF,INF,INF,30,INF,INF,INF,INF,0 ,20,INF,INF},
    
39.     {INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,20,0 ,20,INF},
    
40.     {INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,20,INF,20,0 ,40},
    
41.     {INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,40,0 }
    
42.     };
    
43.     /*
    
44.                
    
45.         int begin=0;   
    
46.         int end=4;   
    
47.         graph.findCheapestPath(begin,end,matrix);   
    
48.         List< Integer> list=graph.result;   
    
49.         System.out.println(begin+" to "+end+",the cheapest path is:");   
    
50.         System.out.println(list.toString());   
    
51.         System.out.println(graph.dist[begin][end]);   
    
52.     }   
    
53.   
    
54.     public  void findCheapestPath(int begin,int end,int[][] matrix){   
    
55.         floyd(matrix);   
    
56.         result.add(begin);   
    
57.         findPath(begin,end);   
    
58.         result.add(end);   
    
59.     }   
    
60.       
    
61.     public void findPath(int i,int j){   
    
62.         int k=path[i][j];   
    
63.         if(k==-1)return;   
    
64.         findPath(i,k);   //递归
    
65.         result.add(k);   
    
66.         findPath(k,j);   
    
67.     }   
    
68.     public  void floyd(int[][] matrix){   
    
69.         int size=matrix.length;   
    
70.         //initialize dist and path   
    
71.         for(int i=0;i< size;i++){   
    
72.             for(int j=0;j< size;j++){   
    
73.                 path[i][j]=-1;   
    
74.                 dist[i][j]=matrix[i][j];   
    
75.             }   
    
76.         }   
    
77.         for(int k=0;k< size;k++){   
    
78.             for(int i=0;i< size;i++){   
    
79.                 for(int j=0;j< size;j++){   
    
80.                     if(dist[i][k]!=INF&&   
    
81.                         dist[k][j]!=INF&&   
    
82.                         dist[i][k]+dist[k][j]< dist[i][j]){
    
83.                         dist[i][j]=dist[i][k]+dist[k][j];   
    
84.                         path[i][j]=k;   
    
85.                     }   
    
86.                 }   
    
87.             }   
    
88.         }   
    
89.            
    
90.     }   
    
91.       
    
92.     public FloydInGraph(int size){   
    
93.         this.path=new int[size][size];   
    
94.         this.dist=new int[size][size];   
    
95.     }   
    
96. }  
    

复制代码

运行结果：
0 to 4,the cheapest path is:
[0, 3, 4]
40  最短距离有三种情况：
１、两点的直达距离最短。（如下图<v,x>）
２、两点间只通过一个中间点而距离最短。（图<v,u>）
３、两点间用通过两各以上的顶点而距离最短。（图<v,w>）  对于第一种情况：
    在初始化的时候就已经找出来了且以后也不会更改到。

对于第二种情况：
    弗洛伊德算法的基本操作就是对于每一对顶点，遍历所有其它顶点，看看可否通过这一个顶点让这对顶点距离更短

对于第三种情况：
      如下图的五边形，可先找一点（比如x，使<v,u>=2），就变成了四边形问题，再找一点（比如y,使<u,w>=2），可变成三角形问题了（v,u,w），也就变成第二种情况了，由此对于n边形也可以一步步转化成四边形三角形问题。（这里面不用担心哪个点要先找哪个点要后找，因为找了任一个点都可以使其变成（n－1）边形的问题）。  
此图的一个运行结果:
D:        utu>java FloydInGraph
10 to 14,the cheapest path is:
[10, 11, 12, 15, 14]
70

  
  
   
   

     
   

     
   
  

复制代码

源码下载：http://file.javaxxz.com/2014/12/6/000712062.zip