Day599.弗洛伊德算法 -数据结构和算法Java

弗洛伊德算法

• 求最短路径算法（ 各个节点到其他节点的最短路径）
• 时间复杂度为n^3
• 通过三个for循环：
  • 对中间节点遍历
  • 对开始节点遍历
  • 对终点节点遍历

一、介绍

二、思想

三、代码实现

package com.achang.algorithm;

import java.util.Arrays;

/**
 * 弗洛伊德算法
 */
public class Floyd {
    public static void main(String[] args) {
        char[] vertex = {'a', 'b', 'c', 'd', 'e', 'f', 'g'};
        final int N = 65535;//不可达常量数字
        int[][] matrix = {
                // a b c d e f g
                {0, 5, 7, N, N, N, 2},//a
                {5, 0, N, 9, N, N, 3},//b
                {7, N, 0, N, 8, N, N},//c
                {N, 9, N, 0, N, 4, N},//d
                {N, N, 8, N, 0, 5, 4},//e
                {N, N, N, 4, 5, 0, 6},//f
                {2, 3, N, N, 4, 6, 0}//g
        };
        Graph1 graph1 = new Graph1(vertex.length, matrix, vertex);
        graph1.showPreArr();
        graph1.showDisArr();
        System.out.println("==========");
        graph1.floyd();
        graph1.showPreArr();
        graph1.showDisArr();
    }


}


//图结构
class Graph1 {
    private char[] vertex;//存放节点的数组
    private int[][] dis;//保存从各个节点出发到其他节点的距离，最后的结果在这里
    private int[][] pre;//保存到达目标节点的前驱节点

    /**
     * @param length 节点数量
     * @param matrix 初始的保存从各个节点出发到其他节点的距离的临界矩阵
     * @param vertex 节点数组
     */
    public Graph1(int length, int[][] matrix, char[] vertex) {
        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数组
     */
    public void showPreArr() {
        System.out.println("遍历pre数组===");
        for (int[] pr : pre) {
            System.out.println(Arrays.toString(pr));
        }
    }

    /**
     * 遍历dis数组
     */
    public void showDisArr() {
        System.out.println("遍历dis数组===");
        for (int[] di : dis) {
            System.out.println(Arrays.toString(di));
        }
    }

    /**
     * 遍历dis数组和pre数组
     */
    public void show() {
        for (int i = 0; i < pre.length; i++) {
            //输出dis数组
            for (int i1 = 0; i1 < dis.length; i1++) {
                System.out.print(dis[i][i1] + "");
            }
            System.out.println();
            //输出pre数组
            for (int i1 = 0; i1 < dis.length; i1++) {
                System.out.print(pre[i][i1] + "");
            }
            System.out.println();
        }
    }

    //弗洛伊德算法，求各个节点到其他节点的最短路径
    public void floyd(){
        int len = 0;//变量保存距离
        //对中间节点遍历，k就是中间节点的下标
        for (int k = 0; k < dis.length; k++) {
            //对下标为j节点的开始节点遍历[a,b,c,d,e,f,g]
            for (int i = 0; i < dis.length; i++) {
                //对终点节点遍历，k就是终点节点的下标
                for (int j = 0; j < dis.length; j++) {
                    len = dis[i][k]+dis[k][j];//求出从i节点出发，经过为k的中间节点，到达最终节点j节点的距离
                    //dis[i][j]直连距离：下标i为的出发节点，到下标j的终点节点的距离
                    if (len < dis[i][j]){
                        dis[i][j] = len;
                        pre[i][j] = pre[k][j];
                    }
                }
            }
        }
    }

}