Java十大算法之弗洛伊德算法

1.弗洛伊德(Floyd)算法介紹:

(1)和Dijkstra算法一樣,弗洛伊德算法也是一種用于尋找給定的權重圖中頂點間最短路徑的算法,與迪傑斯特拉算法的差別是:迪傑斯特拉算法通過標明的被通路點,求出從出發通路頂點到其他頂點的最短路徑.弗洛伊德算法中每一個頂點都是出發通路點,是以需要将每一個頂點看做被通路頂點,求出每一個頂點到其他頂點的最短路徑.

2.思路分析

設定頂點vi到頂點vk的最短路徑已知為lik,頂點vk到vj的最短路徑已知為lkj,頂點vi到vk的路徑為Lij,則vi到vj的最短路徑為:min((lik+lkj),lij),vk的取值為所有的頂點,則可獲得vi到vj的最短路徑.

接下裡用圖例進行一下說明:

上圖的N表示不可以直接到達

弗洛伊的算法的步驟:

第一輪循環中,以A(下标為0),作為中間頂點,即把A作為中間頂點的所有情況都進行比那裡,就會得到更新的距離表和前驅關系表

分析以A為頂點的所有情況(單向的):

CAG距離為9

CAB距離為12

BAG距離為7

更新的距離表和前驅關系表

此次以A為頂點,依次将所有的點作為頂點,找出最小值即可

3實戰

案例:

代碼實作:

package com.self.tenAlgorithm;

import java.util.Arrays;

public class FloydAlgorithm {
    final static int N = 65535;
    public static void main(String[] args) {
        char[] vertex = {'A','B','C','D','E','F','G'};
        //建立鄰接矩陣
        int[][] matrix = new int[vertex.length][vertex.length];
        matrix[0] = new int[]{0,5,7,N,N,N,2};
        matrix[1] = new int[]{5,0,N,9,N,N,3};
        matrix[2] = new int[]{7,N,0,N,8,N,N};
        matrix[3] = new int[]{N,9,N,0,N,4,N};
        matrix[4] = new int[]{N,N,8,N,0,5,4};
        matrix[5] = new int[]{N,N,N,4,5,0,6};
        matrix[6] = new int[]{2,3,N,N,4,6,0};
        Graph0 graph = new Graph0(vertex, vertex.length,matrix);
        graph.floyd();
        graph.show();
    }
}
//建立圖
class Graph0{
    private char[] vertex;  //存放頂點屬主
    private int[][] dis;  //儲存,從各個頂點出發到其他頂點的距離,最後的結果,也是保留在該數組
    private int[][] pre;  //儲存到達目标頂點的前驅節點

    /**
     * 功能: 構造器
     * @param vertex  頂點數組
     * @param length  大小
     * @param matrix  領接矩陣
     */
    public Graph0(char[] vertex, int length,int[][] matrix) {
        this.vertex = vertex;
        this.dis = matrix;
        this.pre = new int[length][length];
        //對pre數組初始化,注意存放的是前驅頂點的下标
        for (int i = 0; i < length; i++) {
            Arrays.fill(pre[i],i);
        }
    }

    /**
     * 功能:顯示pre數組和dis數組
     */
    public void show(){
        char[] vertex = {'A','B','C','D','E','F','G'};
        for (int k = 0; k < dis.length; k++) {
            //先将pre數組輸出的一行
            for (int i = 0; i < dis.length; i++) {
                System.out.print(vertex[pre[k][i]]+" ");
            }
            System.out.println();
            for (int i = 0; i < dis.length; i++) {
                System.out.print("("+vertex[k]+"到"+vertex[i]+"的最短路徑是"+dis[k][i]+") ");
            }
            System.out.println();
            System.out.println();
        }
    }

    /**
     * 弗洛伊德算法實作
     */
    public void floyd(){
        int len = 0;  //變量儲存距離
        //對中間頂點周遊 k就是中間頂點的下标
        for (int k = 0; k < dis.length; k++) {
            //從i頂點開始出發
            for (int i = 0; i < dis.length; i++) {
                //到達j頂點
                for (int j = 0; j < dis.length; j++) {
                    len = dis[i][k] + dis[k][j];
                    if(len < dis[i][j]){
                        dis[i][j] = len;  //更新距離
                        pre[i][j] = pre[k][j];  //更新前驅節點
                    }
                }
            }
        }
    }
}