欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

算法:通过弗洛伊德(Floyd)算法,求出图中任意两个顶点的最短路径

程序员文章站 2024-03-15 18:54:12
...

之前我给大家分享过用迪杰斯特拉(Dijkstra)算法求图的最短路径(点我去看看),今天我再给大家分享一个也是求图的最短路径的弗洛伊德(Floyd)算法

这两个算法都是求图的最短路径,有什么区别呢?
1、Dijkstra算法是求图中一个点到其他所有点的最短路径,Floyd算法是求图中任意两个顶点之间的最短路径
2、Dijkstra算法是通过贪婪算法来实现的,Floyd算法是通过动态规划算法实现的
3、Dijkstra算法的图,所有边的权重不能为负值,Floyd算法的图在不存在负值圈的前提下可以存在负的权重
4、Dijkstra算法在稀疏图上求最短路径更有效率,Floyd算法在稠密图上求最短路径更有效率
5、Dijkstra算法的代码实现比较复杂,Floyd算法的代码实现比较简单

下面是一个图,有A到G七个顶点,顶点间连通用直线连接,直线上的数字代表两点间的权重,可以理解为路程、运输成本等概念,最短路径也就是权重和最小的路径:
算法:通过弗洛伊德(Floyd)算法,求出图中任意两个顶点的最短路径
下面的这个矩阵叫邻接矩阵,中间的数字是两个顶点的权重,也就是左边顶点到上面顶点的权重,就是左边顶点和上面顶点交叉的那个数字值。对角线全部为0,也就是顶点自己到自己的权重是0,INF代表无穷大,代表这两点之间不连通。这个邻接矩阵在接下来的代码中是以二维数组来实现的,INF则用Integer.MAX_VALUE来表示,也就是int的最大值:
算法:通过弗洛伊德(Floyd)算法,求出图中任意两个顶点的最短路径
下面是Floyd算法的Java代码实现,具体的算法精髓都在代码和其间的详细注释中。读者可以复制代码到IDE中运行,用DEBUG模式来研究算法的具体实现过程,最后控制台会输出示例图中任意两个顶点的最短路径信息:

/**
 * @author LiYang
 * @ClassName FloydAlgorithm
 * @Description Floyd(弗洛伊德)算法求最短路径
 * @date 2019/10/25 10:46
 */
public class FloydAlgorithm {

    /**
     * 用Floyd(弗洛伊德)算法求出所有顶点对的最短路径
     * @param source 图的邻接矩阵
     * @param distance Floyd(弗洛伊德)算法的距离表
     * @param path Floyd(弗洛伊德)算法的路径表
     */
    public static void floydAlgorithm(int[][] source, int [][] distance, int[][] path){
        //矩阵的边长
        int length = source.length;
        
        //初始化距离表和路径表
        for (int i = 0; i < length; i++) {
            for (int j = 0; j < length; j++) {
                //复制矩阵图到距离表
                distance[i][j] = source[i][j];
                
                //初始化路径表
                path[i][j] = j;
            }
        }
        
        //重要:运行Floyd(弗洛伊德)算法求所有顶点对的最短路径
        for (int k = 0; k < length; k++) {
            for (int i = 0; i < length; i++) {
                for (int j = 0; j < length; j++) {
                    //如果当前中间顶点的距离小于之前的距离
                    //且中间顶点的两边距离不为无穷大(int最大值)
                    if (distance[i][k] != Integer.MAX_VALUE 
                            && distance[k][j] != Integer.MAX_VALUE 
                            && distance[i][j] > distance[i][k] + distance[k][j]){
                        
                        //更新距离表
                        distance[i][j] = distance[i][k] + distance[k][j];
                        
                        //更新路径表
                        path[i][j] = path[i][k];
                    }
                }
            }
        }
    }

    /**
     * 将Floyd(弗洛伊德)算法的距离表和路径表,解析为任意两点间的最短路径距离和路径图
     * @param distance Floyd(弗洛伊德)算法的距离表
     * @param path Floyd(弗洛伊德)算法的路径表
     * @param vertexName 顶点名字(以路径表中数字为下标取)
     */
    public static void parseShortestPath(int[][] distance, int[][] path, String[] vertexName){
        for (int i = 0; i < path.length; i++) {
            for (int j = 0; j < path.length; j++) {
                
                //出发点和目的点不一样,才打印信息
                //自己到自己,没有意义
                if (i != j){
                    //下一站的顶点
                    int next = path[i][j];
                    
                    //记录路径,并加入出发点
                    StringBuffer route = new StringBuffer(vertexName[i]);

                    //重要:只要未到达目的点
                    while (next != j){
                        //加入当前顶点
                        route.append(" -> ").append(vertexName[next]);
                        
                        //更新下一站顶点
                        //重要:每次都是找path表的第j列,要么找到下一个顶点,要么找到目的顶点
                        next = path[next][j];
                    }
                    
                    //最后加入目的节点
                    route.append(" -> ").append(vertexName[j]);

                    //输出两个顶点的最短距离,以及最短路径
                    System.out.println(String.format("%s到%s的最短距离为%d,最短路径:%s", 
                            vertexName[i], vertexName[j], distance[i][j], route.toString()));
                }
            }
        }
    }

    /**
     * 获取示例图的邻接矩阵
     * @return
     */
    public static int[][] initGraphMatrix(){
        //无穷大距离
        final int INF = Integer.MAX_VALUE;
        
        //生成示例图的邻接矩阵
        int[][] matrix = new int[][]{
                {0, 12, INF, INF, INF, 16, 14},
                {12, 0, 10, INF, INF, 7, INF},
                {INF, 10, 0, 3, 5, 6, INF},
                {INF, INF, 3, 0, 4, INF, INF},
                {INF, INF, 5, 4, 0, 2, 8},
                {16, 7, 6, INF, 2, 0, 9},
                {14, INF, INF, INF, 8, 9, 0}
        };
        
        //返回图的邻接矩阵
        return matrix;
    }

    /**
     * 运行Floyd(弗洛伊德)算法求出所有顶点对的最短路径
     * 提示:如果需要运行自己的图,则需要重新定义initGraphMatrix()
     * 方法里面的邻接矩阵,并重新定义顶点名数组String[] vertexName
     * @param args
     */
    public static void main(String[] args) {
        //生成示例图中的邻接矩阵(自定义邻接矩阵,改下面的方法的返回值)
        int[][] matrix = initGraphMatrix();
        
        //Floyd(弗洛伊德)算法的距离表
        int[][] distance = new int[matrix.length][matrix.length];
        
        //Floyd(弗洛伊德)算法的路径表
        int[][] path = new int[matrix.length][matrix.length];
        
        //运行Floyd(弗洛伊德)算法
        floydAlgorithm(matrix, distance, path);
        
        //邻接矩阵的下标对应的顶点名字(自定义邻接矩阵,改下面字符串数组)
        String[] vertexName = new String[]{"A", "B", "C", "D", "E", "F", "G"};
        
        //根据距离表、路径表、名字数组,解析输出任意两点的最短距离和最短路径
        parseShortestPath(distance, path, vertexName);
    }
    
}

运行上面代码的main方法,控制台将会输出示例图中的任意两顶点之间的最短路径详细信息:

A到B的最短距离为12,最短路径:A -> B
A到C的最短距离为22,最短路径:A -> B -> C
A到D的最短距离为22,最短路径:A -> F -> E -> D
A到E的最短距离为18,最短路径:A -> F -> E
A到F的最短距离为16,最短路径:A -> F
A到G的最短距离为14,最短路径:A -> G
B到A的最短距离为12,最短路径:B -> A
B到C的最短距离为10,最短路径:B -> C
B到D的最短距离为13,最短路径:B -> C -> D
B到E的最短距离为9,最短路径:B -> F -> E
B到F的最短距离为7,最短路径:B -> F
B到G的最短距离为16,最短路径:B -> F -> G
C到A的最短距离为22,最短路径:C -> B -> A
C到B的最短距离为10,最短路径:C -> B
C到D的最短距离为3,最短路径:C -> D
C到E的最短距离为5,最短路径:C -> E
C到F的最短距离为6,最短路径:C -> F
C到G的最短距离为13,最短路径:C -> E -> G
D到A的最短距离为22,最短路径:D -> E -> F -> A
D到B的最短距离为13,最短路径:D -> C -> B
D到C的最短距离为3,最短路径:D -> C
D到E的最短距离为4,最短路径:D -> E
D到F的最短距离为6,最短路径:D -> E -> F
D到G的最短距离为12,最短路径:D -> E -> G
E到A的最短距离为18,最短路径:E -> F -> A
E到B的最短距离为9,最短路径:E -> F -> B
E到C的最短距离为5,最短路径:E -> C
E到D的最短距离为4,最短路径:E -> D
E到F的最短距离为2,最短路径:E -> F
E到G的最短距离为8,最短路径:E -> G
F到A的最短距离为16,最短路径:F -> A
F到B的最短距离为7,最短路径:F -> B
F到C的最短距离为6,最短路径:F -> C
F到D的最短距离为6,最短路径:F -> E -> D
F到E的最短距离为2,最短路径:F -> E
F到G的最短距离为9,最短路径:F -> G
G到A的最短距离为14,最短路径:G -> A
G到B的最短距离为16,最短路径:G -> F -> B
G到C的最短距离为13,最短路径:G -> E -> C
G到D的最短距离为12,最短路径:G -> E -> D
G到E的最短距离为8,最短路径:G -> E
G到F的最短距离为9,最短路径:G -> F