弗洛伊德（Floyd）算法求任意两点间的最短距离（JAVA）_裸奔

http://blog.sina.com.cn/u/1669256124

首页博文目录关于我

个人资料

微博

加好友发纸条

写留言加关注

博客等级：
博客积分：

博客访问：
关注人气：
获赠金笔：0支
赠出金笔：0支
荣誉徽章：

正文字体大小：大中小

弗洛伊德（Floyd）算法求任意两点间的最短距离（JAVA）

(2012-12-17 00:05:13)

标签：

此图

it

floyd

分类：数据结构

Floyd-Warshall算法（Floyd-Warshall algorithm）是解决任意两点间的最短路径的一种算法，可以正确处理带权有向图或负权的最短路径问题

解决此问题有两种方法：
其一是分别以图中每个顶点为源点共调用n次算法；
其二是采用Floyd算法。

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

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

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

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

dist(n-1)[i][j]就是vi到vj的最短路径长度。

http://www.java3z.com/cwbwebhome/article/article1/img13/7d32f816-495b-3f4a-b96e-53053e7c8f12.png

import java.util.ArrayList;

import java.util.List;

public class FloydInGraph {

    private static int INF=Integer.MAX_VALUE;

         //dist[i][j]=INF<==>i 和 j之间没有边

    private int[][] dist;

         //顶点i 到 j的最短路径长度，初值是i到j的边的权重

    private int[][] path;

    private List< Integer> result=new ArrayList< Integer>();

    public static void main(String[] args) {

        FloydInGraph graph=new FloydInGraph(5);

        int[][] matrix={

                {INF,30,INF,10,50},

                {INF,INF,60,INF,INF},

                {INF,INF,INF,INF,INF},

                {INF,INF,INF,INF,30},

                {50,INF,40,INF,INF},

};

              /* 最下面的图

           int[][] matrix = {

    {0 ,20,INF,INF,20,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF},

    {20,0 ,30,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF},

    {INF,30,0 ,20,INF,30,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF},

    {INF,INF,20,0 ,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF},

    {20,INF,INF,INF,0 ,10,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF},

    {INF,INF,30,INF,10,0 ,20,50,INF,INF,INF,INF,INF,INF,INF,INF,INF},

    {INF,INF,INF,INF,INF,20,0 ,40,10,INF,INF,INF,INF,INF,INF,INF,INF},

    {INF,INF,INF,INF,INF,50,40,0 ,INF,20,20,INF,INF,INF,INF,INF,INF},

    {INF,INF,INF,INF,INF,INF,10,INF,0 ,20,INF,INF,INF,30,INF,INF,INF},

    {INF,INF,INF,INF,INF,INF,INF,20,20,0 ,20,INF,INF,INF,INF,INF,INF},

    {INF,INF,INF,INF,INF,INF,INF,20,INF,20,0 ,20,INF,INF,INF,INF,INF},

    {INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,20,0 ,10,INF,INF,INF,INF},

    {INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,10,0 ,INF,INF,20,INF},

    {INF,INF,INF,INF,INF,INF,INF,INF,30,INF,INF,INF,INF,0 ,20,INF,INF},

    {INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,20,0 ,20,INF},

    {INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,20,INF,20,0 ,40},

    {INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,40,0 }

};

/*

        int begin=0;

        int end=4;

        graph.findCheapestPath(begin,end,matrix);

        List< Integer> list=graph.result;

        System.out.println(begin+" to "+end+",the cheapest path is:");

        System.out.println(list.toString());

        System.out.println(graph.dist[begin][end]);

    public  void findCheapestPath(int begin,int end,int[][] matrix){

        floyd(matrix);

        result.add(begin);

        findPath(begin,end);

        result.add(end);

    public void findPath(int i,int j){

        int k=path[i][j];

        if(k==-1)return;

        findPath(i,k);   //递归

        result.add(k);

        findPath(k,j);

    public  void floyd(int[][] matrix){

        int size=matrix.length;

        //initialize dist and path

        for(int i=0;i< size;i++){

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

                path[i][j]=-1;

                dist[i][j]=matrix[i][j];

        for(int k=0;k< size;k++){

            for(int i=0;i< size;i++){

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

                    if(dist[i][k]!=INF&&

                        dist[k][j]!=INF&&

                        dist[i][k]+dist[k][j]< dist[i][j]){

                        dist[i][j]=dist[i][k]+dist[k][j];

                        path[i][j]=k;

    public FloydInGraph(int size){

        this.path=new int[size][size];

        this.dist=new int[size][size];

运行结果：

0 to 4,the cheapest path is:

[0, 3, 4]

最短距离有三种情况：
１、两点的直达距离最短。（如下图<v,x>）
２、两点间只通过一个中间点而距离最短。（图<v,u>）
３、两点间用通过两各以上的顶点而距离最短。（图<v,w>）

对于第一种情况：
   在初始化的时候就已经找出来了且以后也不会更改到。

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

对于第三种情况：
     如下图的五边形，可先找一点（比如x，使<v,u>=2），就变成了四边形问题，再找一点（比如y,使<u,w>=2），可变成三角形问题了（v,u,w），也就变成第二种情况了，由此对于n边形也可以一步步转化成四边形三角形问题。（这里面不用担心哪个点要先找哪个点要后找，因为找了任一个点都可以使其变成（n－1）边形的问题）。

http://www.java3z.com/cwbwebhome/article/article1/img13/b72cdbeb-84ba-3586-859b-78bfa104ddf9.gif

http://www.java3z.com/cwbwebhome/article/article1/img13/fkiid.gif

此图的一个运行结果:

D:\tutu>java FloydInGraph
10 to 14,the cheapest path is:
[10, 11, 12, 15, 14]
70

import java.util.ArrayList;

import java.util.List;

public class FloydInGraph {

    private static int INF=Integer.MAX_VALUE;

         //dist[i][j]=INF<==>i 和 j之间没有边

    private int[][] dist;

         //顶点i 到 j的最短路径长度，初值是i到j的边的权重

    private int[][] path;

    private List< Integer> result=new ArrayList< Integer>();

    public static void main(String[] args) {

        FloydInGraph graph=new FloydInGraph(5);

        int[][] matrix={

                {INF,30,INF,10,50},

                {INF,INF,60,INF,INF},

                {INF,INF,INF,INF,INF},

                {INF,INF,INF,INF,30},

                {50,INF,40,INF,INF},

};

         

       private static int INF=Integer.MAX_VALUE;

         //dist[i][j]=INF<==>no edges between i and j

       private int[][] dist;

         //the distance between i and j.At first,dist[i][j] is the weight of edge [i,j]  

      private int[][] path;  

       private List result=new ArrayList();

     

      public static void main(String[] args) {

               FloydInGraph graph=new FloydInGraph(5);

                int[][] matrix={

                               {INF,30,INF,10,50},

                            {INF,INF,60,INF,INF},

                          {INF,INF,INF,INF,INF},

                         {INF,INF,INF,INF,30},

                          {50,INF,40,INF,INF},

           };

             int begin=0;

           int end=4;

             graph.findCheapestPath(begin,end,matrix);

              List list=graph.result;

               System.out.println(begin+" to "+end+",the cheapest path is:");

         System.out.println(list.toString());

           System.out.println(graph.dist[begin][end]);

    }




     public  void findCheapestPath(int begin,int end,int[][] matrix){

              floyd(matrix);

         result.add(begin);

             findPath(begin,end);

           result.add(end);

       }

  

      public void findPath(int i,int j){

             int k=path[i][j];

              if(k==-1)return;

               findPath(i,k);

         result.add(k);

         findPath(k,j);

 }

      public  void floyd(int[][] matrix){

           int size=matrix.length;

                //initialize dist and path

             for(int i=0;i

                      for(int j=0;j

                              path[i][j]=-1;

                         dist[i][j]=matrix[i][j];

                       }

              }

              for(int k=0;k

                      for(int i=0;i

                              for(int j=0;j

                                      if(dist[i][k]!=INF&&

                                           dist[k][j]!=INF&&

                                              dist[i][k]+dist[k][j]dist[i][j]-->longestPath

                                             dist[i][j]=dist[i][k]+dist[k][j];

                                              path[i][j]=k;

                                  }

                              }

                      }

              }

          

      }

  

      public FloydInGraph(int size){

         this.path=new int[size][size];

         this.dist=new int[size][size];

 }

}

阅读┊ 收藏 ┊ 喜欢 ▼ ┊打印┊举报/Report

前一篇：普里姆算法

后一篇：背包问题的c语言实现

新浪BLOG意见反馈留言板　欢迎批评指正