package com.yg.algorithm;/*
@author  Mu_Mu
@date    2020/3/23  9:56
*/
public class FloydAlgorithm {
    private static final int MAX=10000;
    public static void main(String[] args) {
        char[] vertexs = {'A', 'B', 'C', 'D', 'E'};
        int[][] matrix = {{0, MAX, MAX, 5, 2}, {MAX, 0, 8, MAX, 3}
                , {MAX, 8, 0, MAX, 4}, {5, MAX, MAX, 0, 9},{2,3,4,9,0}};
        FGraph fGraph = new FGraph(vertexs, matrix);
        fGraph.floyd();
        fGraph.show();
    }
}
class FGraph {
    private char[]vertexs;//存放頂點
    private int [][]dis;//每個頂點之間的距離
    private int[][]pre;//存放前驅(qū)頂點
    public FGraph(char[] vertexs, int[][] dis) {
        this.vertexs = vertexs;
        this.dis = dis;
        pre=new int [vertexs.length][vertexs.length];
        //初始化前驅(qū)頂點
        for (int i = 0; i < vertexs.length; i++) {
            for (int j = 0; j < vertexs.length; j++) {
                pre[i][j]=i;
            }
        }
    }
    //弗洛伊德算法
    public void floyd() {
        int len=0;
        //i,遍歷中間頂點,3層循環(huán)的意義就是j通過i到k
        for (int i = 0; i < vertexs.length; i++) {
            //j代表出發(fā)節(jié)點
            for (int j = 0; j < vertexs.length; j++) {
                //k代表終點頂點
                for (int k = 0; k < vertexs.length; k++) {
                    //記錄j通過i到k的距離
                    len=dis[j][i]+dis[i][k];
                    //比較j通過i到k的距離是否小于j直接到k的距離
                    if (len < dis[j][k]) {
                        dis[j][k]=len;
                        pre[j][k]=pre[i][k];
                    }
                }
            }
        }
    }
    //打印圖
    public void show() {
        for (int i = 0; i < vertexs.length; i++) {
            //打印前驅(qū)頂點
            for (int j = 0; j < vertexs.length; j++) {
                System.out.print(vertexs[pre[i][j]]+"  ");
            }
            System.out.println();
           //打印頂點之間的距離
                for (int k = 0; k < vertexs.length; k++) {
                    System.out.print(vertexs[i]+"到"+vertexs[k]+"的距離為："+dis[i][k]+"  ");
                }
            System.out.println();
        }
        }
    }