package grap;
//04          选择中心点
import java.util.Arrays;

public class Floyd {



    /*
     * 参数adjMatrix：给定连通图的权重矩阵，其中权重为-1表示两个顶点不能直接相连
     * 函数功能：返回所有顶点之间的最短距离权重矩阵
     */
    public void getShortestPaths(int[][] adjMatrix) {
        for(int k = 0;k <adjMatrix.length;k++) {
            for(int i = 0;i < adjMatrix.length;i++) {
                for(int j = 0;j < adjMatrix.length;j++) {
                    if(adjMatrix[i][k] != -1 && adjMatrix[k][j] != -1) {
                        int temp = adjMatrix[i][k] + adjMatrix[k][j];  //含有中间节点k的顶点i到顶点j的距离
                        if(adjMatrix[i][j] == -1 || adjMatrix[i][j] > temp)
                            adjMatrix[i][j] = temp;
                    }
                }
            }
        }
    }

    public static void main(String[] args) throws Exception {
        Floyd test = new Floyd();
        //手动创建图
        char[] data={'A', 'B', 'C', 'D', 'E', 'F', 'G','H','I','J'};
        int verxs=data.length;
        int N=99999999;
        int [][]   adjMatrix=new int[][]{
                {0,N,40,80,N,N,N,N,N,N},
                {N,0,N,70,60,N,20,20,N,N},
                {40,N,0,N,20,80,N,N,N,N},
                {80,70,N,0,60,N,N,N,N,N},
                {N,60,20,20,0,N,N,N,N,N},
                {N,N,80,N,N,0,N,N,10,N},
                {N,20,N,N,N,40,0,50,N,N},
                {N,20,N,N,N,N,N,0,60,90},
                {N,N,N,N,N,10,N,60,0,70},
                {N,N,N,N,N,N,N,90,70,0}};


        test.getShortestPaths(adjMatrix);
        System.out.println("使用Floyd算法得到的所有顶点之间的最短距离权重矩阵为：");
        for(int i = 0;i < adjMatrix.length;i++) {
            for(int j = 0;j < adjMatrix[0].length;j++)
                System.out.print(adjMatrix[i][j]+" ");
            System.out.println();
        }
       findPlace(data,adjMatrix);
    }

    public static void findPlace(char[] data, int[][]  adjMatrix) throws Exception {
        int min = 0;
        int sum = 0;
        int u = -1;
        for(int v = 0; v<adjMatrix.length;v++){
            sum = 0;
            for(int w =0;w<adjMatrix.length;w++)
            sum += adjMatrix[v][w];
            if(min<sum){
                min = sum;
                u= v;
            }
        }
        System.out.println(" 应该选择"+data[u]+"城市为中心" );

    }
}