package dijkstraV2;

import java.util.ArrayList;
import java.util.List;

class FloydInGraph {

private static int INF = Integer.MAX_VALUE;
//dist[i][j]=INF<==>i 和 j之间没有边
private int[][] dist;
//顶点i 到 j的最短路径长度，初值是i到j的边的权重
private int[][] path;
private List<Integer> result = new ArrayList<Integer>();

public static void main(String[] args) {
    FloydInGraph graph = new FloydInGraph(7);
    String[] strArr = {"b1", "b2", "b7", "b8", "b3", "b4", "b5"};
    int[][] matrix = {
            // b1, b2, b7, b8, b3, b4, b5
            /*0 b1*/{INF, 900, INF, INF, INF, INF, INF},
            /*1 b2*/{900, INF, 400, INF, 100, INF, INF},
            /*2 b7*/{INF, 400, INF, 50, INF, INF, INF},
            /*3 b8*/{INF, INF, 50, INF, INF, INF, INF},
            /*4 b3*/{INF, 100, INF, INF, INF, 200, INF},
            /*5 b4*/{INF, INF, INF, INF, 200, INF, 150},
            /*6 b5*/{INF, INF, INF, INF, INF, 150, INF},
    };
    int begin = 3;
    int end = 6;
    graph.findCheapestPath(begin, end, matrix);
    List<Integer> list = graph.result;
    System.out.println(strArr[begin] + " to " + strArr[end] + ",the cheapest path is:");
    //System.out.println(list.toString());
    StringBuffer sb = new StringBuffer();
    for (Integer idx : list) {
        sb.append(strArr[idx] + "->");
    }
    System.out.println(sb);
    System.out.println(graph.dist[begin][end]);
}

public void findCheapestPath(int begin, int end, int[][] matrix) {
    floyd(matrix);
    result.add(begin);
    findPath(begin, end);
    result.add(end);
}

public void findPath(int i, int j) {
    int k = path[i][j];
    if (k == -1) return;
    findPath(i, k);   //递归
    result.add(k);
    findPath(k, j);
}

public void floyd(int[][] matrix) {
    int size = matrix.length;
    //initialize dist and path
    for (int i = 0; i < size; i++) {
        for (int j = 0; j < size; j++) {
            path[i][j] = -1;
            dist[i][j] = matrix[i][j];
        }
    }
    for (int k = 0; k < size; k++) {
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                if (dist[i][k] != INF && dist[k][j] != INF && dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                    path[i][j] = k;
                }
            }
        }
    }
}

public FloydInGraph(int size) {
    this.path = new int[size][size];
    this.dist = new int[size][size];
}

}