package graph.dijkstra;
 
import java.util.Scanner;
import java.util.Stack;
 
public class Dijkstra {
    static final int MaxVnum = 100;  // 頂點(diǎn)數(shù)最大值
    static final int INF = 0x3f3f3f3f; //無窮大
    static final int dist[] = new int[MaxVnum]; // 最短距離
    static final int p[] = new int[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("請(qǐng)輸入頂點(diǎn)數(shù)：");
        G.vexnum = scanner.nextInt();
        System.out.println("請(qǐng)輸入邊數(shù):");
        G.edgenum = scanner.nextInt();
        System.out.println("請(qǐng)輸入頂點(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++)
                G.Edge[m][n] = INF;
 
        System.out.println("請(qǐng)輸入每條邊依附的兩個(gè)頂點(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 的存儲(chǔ)下標(biāo)
            j = locatevex(G, v);// 查找頂點(diǎn) v 的存儲(chǔ)下標(biāo)
            if (i != -1 && j != -1)
                G.Edge[i][j] = w; //有向圖鄰接矩陣
            else {
                System.out.println("輸入頂點(diǎn)信息錯(cuò)！請(qǐng)重新輸入！");
                G.edgenum++; // 本次輸入不算
            }
        }
    }
 
    static void print(AMGraph G) { // 輸出鄰接矩陣
        System.out.println("圖的鄰接矩陣為：");
        for (int i = 0; i < G.vexnum; i++) {
            for (int j = 0; j < G.vexnum; j++)
                System.out.print(G.Edge[i][j] + "\t");
            System.out.println();
        }
    }
 
    public static void main(String[] args) {
        AMGraph G = new AMGraph();
        int st;
        char u;
        CreateAMGraph(G);
        System.out.println("請(qǐng)輸入源點(diǎn)的信息:");
        Scanner scanner = new Scanner(System.in);
        u = scanner.next().charAt(0);
        ;
        st = locatevex(G, u);//查找源點(diǎn)u的存儲(chǔ)下標(biāo)
        Dijkstra(G, st);
        System.out.println("小明所在的位置:" + u);
 
        for (int i = 0; i < G.vexnum; i++) {
            System.out.print("小明:" + u + " - " + "要去的位置:" + G.Vex[i]);
 
            if (dist[i] == INF)
                System.out.print(" sorry,無路可達(dá)");
            else
                System.out.println(" 最短距離為:" + dist[i]);
        }
        findpath(G, u);
    }
 
    public static void Dijkstra(AMGraph G, int u) {
        for (int i = 0; i < G.vexnum; i++) {
            dist[i] = G.Edge[u][i]; //初始化源點(diǎn)u到其他各個(gè)頂點(diǎn)的最短路徑長(zhǎng)度
            flag[i] = false;
            if (dist[i] == INF)
                p[i] = -1; //源點(diǎn)u到該頂點(diǎn)的路徑長(zhǎng)度為無窮大，說明頂點(diǎn)i與源點(diǎn)u不相鄰
            else
                p[i] = u; //說明頂點(diǎn)i與源點(diǎn)u相鄰，設(shè)置頂點(diǎn)i的前驅(qū)p[i]=u
        }
        dist[u] = 0;
        flag[u] = true;   //初始時(shí)，集合S中只有一個(gè)元素：源點(diǎn)u
        for (int i = 0; i < G.vexnum; i++) {
            int temp = INF, t = u;
            for (int j = 0; j < G.vexnum; j++) //在集合V-S中尋找距離源點(diǎn)u最近的頂點(diǎn)t
                if (!flag[j] && dist[j] < temp) {
                    t = j;
                    temp = dist[j];
                }
            if (t == u) return; //找不到t，跳出循環(huán)
            flag[t] = true;  //否則，將t加入集合
            for (int j = 0; j < G.vexnum; j++)//更新V-S中與t相鄰接的頂點(diǎn)到源點(diǎn)u的距離
                if (!flag[j] && G.Edge[t][j] < INF)
                    if (dist[j] > (dist[t] + G.Edge[t][j])) {
                        dist[j] = dist[t] + G.Edge[t][j];
                        p[j] = t;
                    }
        }
    }
 
    public static void findpath(AMGraph G, char u) {
        int x;
        Stack<Integer> S = new Stack<>();
        System.out.println("源點(diǎn)為：" + u);
 
        for (int i = 0; i < G.vexnum; i++) {
            x = p[i];
            if (x == -1 && u != G.Vex[i]) {
                System.out.println("源點(diǎn)到其它各頂點(diǎn)最短路徑為：" + u + "--" + G.Vex[i] + "    sorry,無路可達(dá)");
                continue;
            }
            while (x != -1) {
                S.push(x);
                x = p[x];
            }
            System.out.println("源點(diǎn)到其它各頂點(diǎn)最短路徑為：");
            while (!S.empty()) {
                System.out.print(G.Vex[S.peek()] + "--");
                S.pop();
            }
            System.out.println(G.Vex[i] + "    最短距離為：" + dist[i]);
        }
    }
}
 
class AMGraph {
    char Vex[] = new char[Dijkstra.MaxVnum];
    int Edge[][] = new int[Dijkstra.MaxVnum][Dijkstra.MaxVnum];
    int vexnum; // 頂點(diǎn)數(shù)
    int edgenum; // 邊數(shù)
}