package graph.floyd;
 
import java.util.Scanner;
 
public class Floyd {
    static final int MaxVnum = 100;  // 頂點(diǎn)數(shù)最大值
    static final int INF = 0x3f3f3f3f; //無窮大
    static final int dist[][] = new int[MaxVnum][MaxVnum]; // 最短距離
    static final int p[][] = new int[MaxVnum][MaxVnum]; // 前驅(qū)數(shù)組
    static final boolean flag[] = new boolean[MaxVnum]; // 如果 s[i] 等于 true，說明頂點(diǎn) i 已經(jīng)加入到集合 S ;否則頂點(diǎn) i 屬于集合 V-S
 
    static int locatevex(AMGraph G, char x) {
        for (int i = 0; i < G.vexnum; i++) // 查找頂點(diǎn)信息的下標(biāo)
            if (x == G.Vex[i])
                return i;
        return -1; // 沒找到
    }
 
    static void CreateAMGraph(AMGraph G) {
        Scanner scanner = new Scanner(System.in);
        int i, j;
        char u, v;
        int w;
        System.out.println("請輸入頂點(diǎn)數(shù)：");
        G.vexnum = scanner.nextInt();
        System.out.println("請輸入邊數(shù):");
        G.edgenum = scanner.nextInt();
        System.out.println("請輸入頂點(diǎn)信息:");
 
        // 輸入頂點(diǎn)信息，存入頂點(diǎn)信息數(shù)組
        for (int k = 0; k < G.vexnum; k++) {
            G.Vex[k] = scanner.next().charAt(0);
        }
        //初始化鄰接矩陣所有值為0，如果是網(wǎng)，則初始化鄰接矩陣為無窮大
        for (int m = 0; m < G.vexnum; m++)
            for (int n = 0; n < G.vexnum; n++)
                if (m != n)
                    G.Edge[m][n] = INF;
                else
                    G.Edge[m][n] = 0; // 注意m==n時，設(shè)置為 0
 
        System.out.println("請輸入每條邊依附的兩個頂點(diǎn)及權(quán)值：");
        while (G.edgenum-- > 0) {
            u = scanner.next().charAt(0);
            v = scanner.next().charAt(0);
            w = scanner.nextInt();
 
            i = locatevex(G, u);// 查找頂點(diǎn) u 的存儲下標(biāo)
            j = locatevex(G, v);// 查找頂點(diǎn) v 的存儲下標(biāo)
            if (i != -1 && j != -1)
                G.Edge[i][j] = w; //有向圖鄰接矩陣
            else {
                System.out.println("輸入頂點(diǎn)信息錯！請重新輸入！");
                G.edgenum++; // 本次輸入不算
            }
        }
    }
 
    static void Floyd(AMGraph G) { // 用 Floyd 算法求有向網(wǎng) G 中各對頂點(diǎn) i 和 j 之間的最短路徑
        int i, j, k;
        for (i = 0; i < G.vexnum; i++)                // 各對結(jié)點(diǎn)之間初始已知路徑及距離
            for (j = 0; j < G.vexnum; j++) {
                dist[i][j] = G.Edge[i][j];
                if (dist[i][j] < INF && i != j)
                    p[i][j] = i;    // 如果 i 和 j 之間有弧，則將 j 的前驅(qū)置為 i
                else p[i][j] = -1;  // 如果 i 和 j 之間無弧，則將 j 的前驅(qū)置為 -1
            }
        for (k = 0; k < G.vexnum; k++)
            for (i = 0; i < G.vexnum; i++)
                for (j = 0; j < G.vexnum; j++)
                    if (dist[i][k] + dist[k][j] < dist[i][j]) { // 從 i 經(jīng) k 到 j 的一條路徑更短
                        dist[i][j] = dist[i][k] + dist[k][j]; // 更新dist[i][j]
                        p[i][j] = p[k][j];   // 更改 j 的前驅(qū)
                    }
    }
 
    static void print(AMGraph G) { // 輸出鄰接矩陣
        int i, j;
        for (i = 0; i < G.vexnum; i++) {//輸出最短距離數(shù)組
            for (j = 0; j < G.vexnum; j++)
                System.out.print(dist[i][j] + "\t");
            System.out.println();
        }
        System.out.println();
        for (i = 0; i < G.vexnum; i++) {//輸出前驅(qū)數(shù)組
            for (j = 0; j < G.vexnum; j++)
                System.out.print(p[i][j] + "\t");
            System.out.println();
        }
    }
 
    static void DisplayPath(AMGraph G, int s, int t) { // 顯示最短路徑
        if (p[s][t] != -1) {
            DisplayPath(G, s, p[s][t]);
            System.out.print(G.Vex[p[s][t]] + "-->");
        }
    }
 
    public static void main(String[] args) {
        char start, destination;
        int u, v;
        AMGraph G = new AMGraph();
        CreateAMGraph(G);
        Floyd(G);
        print(G);
        System.out.print("請依次輸入路徑的起點(diǎn)與終點(diǎn)的名稱：");
        Scanner scanner = new Scanner(System.in);
        start = scanner.next().charAt(0);
        destination = scanner.next().charAt(0);
        u = locatevex(G, start);
        v = locatevex(G, destination);
        DisplayPath(G, u, v);
        System.out.println(G.Vex[v]);
        System.out.println("最短路徑的長度為：" + dist[u][v]);
        System.out.println();
    }
}
 
class AMGraph {
    char Vex[] = new char[Floyd.MaxVnum];
    int Edge[][] = new int[Floyd.MaxVnum][Floyd.MaxVnum];
    int vexnum; // 頂點(diǎn)數(shù)
    int edgenum; // 邊數(shù)
}