弗洛伊德算法(Floyd)

痛定思痛。 2023-07-13 12:23 7阅读 0赞

### 弗洛伊德(Floyd)算法介绍 ###

1.  和Dijkstra算法一样，弗洛伊德(Floyd)算法也是一种用于寻找给定的加权图中顶点间最短路径的算法。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名
2.  弗洛伊德算法(Floyd)计算**图中各个顶点之间的最短路径**
3.  迪杰斯特拉算法用于计算图中某一个顶点到其他顶点的最短路径。
4.  弗洛伊德算法 VS 迪杰斯特拉算法：迪杰斯特拉算法通过选定的被访问顶点，求出从出发访问顶点到其他顶点的最短路径；弗洛伊德算法中每一个顶点都是出发访问点，所以需要将每一个顶点看做被访问顶点，求出从每一个顶点到其他顶点的最短路径。

*  弗洛伊德算法分析

> 1.  设置顶点vi到顶点vk的最短路径已知为Lik，顶点vk到vj的最短路径已知为Lkj，顶点vi到vj的路径为Lij，则vi到vj的最短路径为：min((Lik+Lkj),Lij)，vk的取值为图中所有顶点，则可获得vi到vj的最短路径
> 2.  至于vi到vk的最短路径Lik或者vk到vj的最短路径Lkj，是以同样的方式获得

从上面的介绍不太好理解弗洛伊德算法，其实弗洛伊德算法就是在图中，选取一个顶点作为中间节点，然后遍历穷举该顶点作为中间节点的是时候，其他顶点经过该中间节点到其他顶点的距离比较和他们的的直接距离，如果经过该中间节点的距离小 ，则把该距离更新到对应的集合或数组，同时也记录前驱节点（其实弗洛伊德算法就是3个嵌套for循环，看下面代码示例）

代码示例：

// 图
    public class Graph { 
        // 图的顶点
        private char[] vertex;
        // 图的边，邻接矩阵表示
        private int[][] weight;
    
        public Graph(char[] vertex, int[][] weight) { 
            this.vertex = vertex;
            this.weight = weight;
        }
    
        /** * 获取对应顶点c的在数组的下标 * @param c 顶点的值 * @return 返回顶点的下标，找不到返回-1 */
        public int getPosition(char c) { 
            if (vertex == null || vertex.length == 0) { 
                return -1;
            }
           for (int i = 0; i < vertex.length; i++) { 
                if (vertex[i] == c) { 
                    return i;
                }
           }
           // 找到不到返回-1
            return -1;
        }
    
        public char[] getVertex() { 
            return vertex;
        }
    
        public void setVertex(char[] vertex) { 
            this.vertex = vertex;
        }
    
        public int[][] getWeight() { 
            return weight;
        }
    
        public void setWeight(int[][] weight) { 
            this.weight = weight;
        }
    }

算法核心

/** * 弗洛伊德算法 */
    public class FloydAlgorithm { 
        // 顶点的集合
        private char[] vertex;
        // 各顶点到其他顶点的距离
        private int[][] dis;
        // 保存各顶点到目标顶点的距离
        private int[][] pre;
    
        private Graph graph;
    
        public FloydAlgorithm(Graph graph) { 
            this.graph = graph;
            vertex = graph.getVertex();
            dis = graph.getWeight();
            pre = new int[vertex.length][vertex.length];
            // 对pre数组初始化, 注意存放的是前驱顶点的下标
            for (int i = 0; i < vertex.length; i++) { 
                Arrays.fill(pre[i], i);
            }
    
        }
    
        public void show() { 
            for (int i = 0; i < dis.length; i++) { 
                for (int j = 0; j < dis[i].length; j++) { 
                    System.out.println("出发顶点 "+ vertex[i] + " 到顶点 "+ vertex[j] + "的距离是："+ dis[i][j]);
                }
                System.out.println("==========================");
            }
            System.out.println("///");
            for (int i = 0; i < pre.length; i++) { 
                for (int j = 0; j < pre[i].length; j++) { 
                    System.out.println("出发顶点"+ vertex[i] + "： "+ vertex[j] + "的前驱是："+ vertex[pre[i][j]]);
                }
                System.out.println("==========================");
            }
        }
    
        /** * 弗洛伊德算法核心方法 */
        public void floyd() { 
            int len = 0;
            // 1.选取中间节点，每一个顶点都作为中间节点，
            for (int i = 0; i < vertex.length; i++) { 
                // 作为出发顶点
                for (int m = 0; m < vertex.length; m++) { 
                    // 作为达到顶点
                    for (int n = 0; n < vertex.length; n++) { 
                        // 从m到i的距离 + 从i到n的距离
                        len = dis[m][i] + dis[i][n];
                        // 如果len小于 不经过中间节点i 从m直接到n的距离
                        if (len < dis[m][n]) { 
                            // 则更新从m到n的距离
                            dis[m][n] = len;
                            // 更新m作为出发顶点，n的前驱顶点为i
                            pre[m][n] = pre[i][n];
                        }
                    }
                }
            }
        }
    }

运行结果可以自己打印