package com.yun;

import freemarker.template.utility.DateUtil;
import java.io.BufferedReader;
import java.io.DataOutputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;


public class test {
    /*
     * 弗洛依德算法
     * 参数adjMatrix：给定连通图的权重矩阵，其中权重为10000表示两个顶点不能直接相连
     * 函数功能：返回所有顶点之间的最短距离权重矩阵
     */
    public static 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] != 10000 && adjMatrix[k][j] != 10000) {
                        int temp = adjMatrix[i][k] + adjMatrix[k][j];  //含有中间节点k的顶点i到顶点j的距离
                        if(adjMatrix[i][j] == 10000 || adjMatrix[i][j] > temp)
                            adjMatrix[i][j] = temp;
                    }
                }
            }
        }
    }

    /*
     * 迪杰斯特拉算法
     * 参数adjMatrix：给定连通图的权重矩阵，其中权重为10000表示两个顶点不能直接相连
     * 参数source：以哪一个点为起点 -1< source <matrix.length
     */
    public static void dijstra(int[][] matrix, int source) {
        int MaxValue = 100000;
        //最短路径长度
        int[] shortest = new int[matrix.length];
        //判断该点的最短路径是否求出
        int[] visited = new int[matrix.length];
        //存储输出路径
        String[] path = new String[matrix.length];
        //初始化输出路径
        for (int i = 0; i < matrix.length; i++) {
            path[i] = new String(source + "->" + i);
        }
        //初始化源节点
        shortest[source] = 0;
        visited[source] = 1;
        for (int i = 1; i < matrix.length; i++) {
            int min = Integer.MAX_VALUE;
            int index = -1;
            for (int j = 0; j < matrix.length; j++) {
                //已经求出最短路径的节点不需要再加入计算并判断加入节点后是否存在更短路径
                if (visited[j] == 0 && matrix[source][j] < min) {
                    min = matrix[source][j];
                    index = j;
                }
            }
            //更新最短路径
            shortest[index] = min;
            visited[index] = 1;
            //更新从index跳到其它节点的较短路径
            for (int m = 0; m < matrix.length; m++) {
                if (visited[m] == 0 && matrix[source][index] + matrix[index][m] < matrix[source][m]) {
                    matrix[source][m] = matrix[source][index] + matrix[index][m];
                    path[m] = path[index] + "->" + m;
                }
            }
        }
        //打印最短路径
        for (int i = 0; i < matrix.length; i++) {
            if (i != source) {
                if (shortest[i] == MaxValue) {
                    System.out.println(source + "到" + i + "不可达");
                } else {
                    System.out.println(source + "到" + i + "的最短路径为：" + path[i] + "，最短距离是：" + shortest[i]);
                }
            }
        }
    }

    public static void main(String[] args) {
        int[][] adjMatrix = {
                {0,5,7,100000,100000,100000,2},
                {5,0,100000,9,100000,100000,3},
                {7,100000,0,100000,8,100000,100000},
                {100000,9,100000,0,100000,4,100000},
                {100000,100000,8,100000,0,5,4},
                {100000,100000,100000,4,5,0,6},
                {2,3,100000,100000,4,6,0}
        };
        dijstra(adjMatrix, 3);
        int[][] floydMatrix = {
                {0,5,7,100000,100000,100000,2},
                {5,0,100000,9,100000,100000,3},
                {7,100000,0,100000,8,100000,100000},
                {100000,9,100000,0,100000,4,100000},
                {100000,100000,8,100000,0,5,4},
                {100000,100000,100000,4,5,0,6},
                {2,3,100000,100000,4,6,0}
        };
        getShortestPaths(floydMatrix);
        int s = 0;
        System.out.println("  A  B  C  D  E  F  G");
        for (int[] i : floydMatrix) {
           System.out.println((char)('A'+s)+ Arrays.toString(i));
           s++;
        }
    }
}

// 运行结果
3到0的最短路径为：3->5->6->0，最短距离是：12
3到1的最短路径为：3->1，最短距离是：9
3到2的最短路径为：3->5->4->2，最短距离是：17
3到4的最短路径为：3->5->4，最短距离是：9
3到5的最短路径为：3->5，最短距离是：4
3到6的最短路径为：3->5->6，最短距离是：10
  A  B  C  D  E  F  G
A[0, 5, 7, 12, 6, 8, 2]
B[5, 0, 12, 9, 7, 9, 3]
C[7, 12, 0, 17, 8, 13, 9]
D[12, 9, 17, 0, 9, 4, 10]
E[6, 7, 8, 9, 0, 5, 4]
F[8, 9, 13, 4, 5, 0, 6]
G[2, 3, 9, 10, 4, 6, 0]

　　弗洛伊德算法是3个for循环，判断经历了中间点的两点路径和的长度是否比两点直接长度短 如果短就存储值（如果两点之间没有中间点就跳出循环） 时间复杂度是O(n^3) 可以得出任意点到任意点的最短距离

　　迪杰斯特拉算法是先选一个起始点，然后将未计算的点放到一个数组T，已选择的点放到数组V，然后一个点一个点的选，每选一个点，就会更新起始点到关联到的其他点的最短距离，最后选完所有点即可得出起点到其他点的最短距离，时间复杂度是O(n^2)，只可以计算起始点到其他点的最短距离，并且不能计算权重值为负数的图

　　其实遍历每一个点，调用迪杰斯特拉算法就可以得出任意点到任意点的距离，并且时间复杂度由O(n^2)变为O(n^3)