import java.util.*;

class Graph {
    private int V; // 圖中頂點的數(shù)量
    private int[][] matrix; // 用鄰接矩陣表示圖

    Graph(int v) {
        V = v;
        matrix = new int[V][V];
    }

    void addEdge(int src, int dest, int weight) {
        matrix[src][dest] = weight;
        matrix[dest][src] = weight;
    }

    int findMinDistance(int[] distance, boolean[] shortestPathTreeSet) {
        int minDistance = Integer.MAX_VALUE;
        int minIndex = -1;

        for (int i = 0; i < V; i++) {
            if (!shortestPathTreeSet[i] && distance[i] <= minDistance) {
                minDistance = distance[i];
                minIndex = i;
            }
        }

        return minIndex;
    }

    void printShortestPaths(int[] distance) {
        System.out.println("節(jié)點\t\t最短路徑");
        for (int i = 0; i < V; i++) {
            System.out.println(i + "\t\t" + distance[i]);
        }
    }

    void dijkstra(int src) {
        int[] distance = new int[V];
        boolean[] shortestPathTreeSet = new boolean[V];

        for (int i = 0; i < V; i++) {
            distance[i] = Integer.MAX_VALUE;
            shortestPathTreeSet[i] = false;
        }

        distance[src] = 0;

        for (int count = 0; count < V - 1; count++) {
            int u = findMinDistance(distance, shortestPathTreeSet);
            shortestPathTreeSet[u] = true;

            for (int v = 0; v < V; v++) {
                if (!shortestPathTreeSet[v] && matrix[u][v] != 0
                        && distance[u] != Integer.MAX_VALUE
                        && distance[u] + matrix[u][v] < distance[v]) {
                    distance[v] = distance[u] + matrix[u][v];
                }
            }
        }

        printShortestPaths(distance);
    }

    public static void main(String args[]) {
        Graph g = new Graph(6);

        g.addEdge(0, 1, 4);
        g.addEdge(0, 2, 3);
        g.addEdge(1, 3, 2);
        g.addEdge(1, 2, 1);
        g.addEdge(2, 3, 4);
        g.addEdge(3, 4, 2);
        g.addEdge(4, 5, 6);

        System.out.println("Dijkstra算法最短路徑結(jié)果：");

        g.dijkstra(0);
    }
}