import java.util.*;
//java实现一个图的最短路径算法
public class Test_34 {
//    定义一个常量INF，表示无穷大。
    private static final int INF = Integer.MAX_VALUE;
//    定义一个方法dijkstra，接受一个二维数组图和一个起始节点作为参数。
    public static void dijkstra(int[][] graph, int start) {
//        获取图的顶点个数。
        int numVertices = graph.length;
//        创建一个数组dist，用于存储从起始节点到每个节点的最短距离
        int[] dist = new int[numVertices];
//        创建一个数组visited，用来标记每个节点是否已经访问过。
        boolean[] visited = new boolean[numVertices];
//        将dist数组填充为无穷大。
        Arrays.fill(dist, INF);
//        将起始节点到自身的距离设为0
        dist[start] = 0;

//        利用循环来遍历每个节点。
        for (int i = 0; i < numVertices - 1; i++) {
//            获取未访问过的节点中距禧当前节点最近的节点。
            int minVertex = getMinVertex(dist, visited);
//            将该节点标记为已访问。
            visited[minVertex] = true;
//            在内层循环中，遍历当前节点的邻居节点，更新到达邻居节点的最短距离。
            for (int j = 0; j < numVertices; j++) {
                if (!visited[j] && graph[minVertex][j] != 0 && dist[minVertex] != INF &&
                        dist[minVertex] + graph[minVertex][j] < dist[j]) {
                    dist[j] = dist[minVertex] + graph[minVertex][j];
                }
            }
        }

        printShortestPath(start, dist);
    }
//    定义一个方法，用来获取未访问过的最近节点。
    private static int getMinVertex(int[] dist, boolean[] visited) {
        int minDist = INF;
        int minVertex = -1;

        for (int i = 0; i < dist.length; i++) {
            if (!visited[i] && dist[i] < minDist) {
                minDist = dist[i];
                minVertex = i;
            }
        }

        return minVertex;
    }
//    定义一个方法，用来打印起始节点到各个节点的最短距离。
    private static void printShortestPath(int start, int[] dist) {
        for (int i = 0; i < dist.length; i++) {
            System.out.println("Shortest distance from node " + start + " to node " + i + " is: " + dist[i]);
        }
    }

    public static void main(String[] args) {
        int[][] graph = {
                {0, 4, 0, 0, 0, 0, 0, 8, 0},
                {4, 0, 8, 0, 0, 0, 0, 11, 0},
                {0, 8, 0, 7, 0, 4, 0, 0, 2},
                {0, 0, 7, 0, 9, 14, 0, 0, 0},
                {0, 0, 0, 9, 0, 10, 0, 0, 0},
                {0, 0, 4, 14, 10, 0, 2, 0, 0},
                {0, 0, 0, 0, 0, 2, 0, 1, 6},
                {8, 11, 0, 0, 0, 0, 1, 0, 7},
                {0, 0, 2, 0, 0, 0, 6, 7, 0}
        };

//        初始化一个示例的图，然后调用dijkstra方法传入起始节点0
        dijkstra(graph, 0);
    }
}