dijkstra算法java代码

以下是 Dijkstra 算法的 Java 代码：

import java.util.*;

public class Dijkstra {

    public static void main(String[] args) {

        int[][] graph = {
            {0, 2, 0, 6, 0},
            {2, 0, 3, 8, 5},
            {0, 3, 0, 0, 7},
            {6, 8, 0, 0, 9},
            {0, 5, 7, 9, 0}
        };

        dijkstra(graph, 0);
    }

    public static void dijkstra(int[][] graph, int source) {

        int n = graph.length;
        int[] dist = new int[n];
        boolean[] visited = new boolean[n];

        for (int i = 0; i < n; i++) {
            dist[i] = Integer.MAX_VALUE;
        }

        dist[source] = 0;

        for (int i = 0; i < n - 1; i++) {

            int u = minDistance(dist, visited);

            visited[u] = true;

            for (int j = 0; j < n; j++) {

                if (!visited[j] &&
                    graph[u][j] != 0 &&
                    dist[u] != Integer.MAX_VALUE &&
                    dist[u] + graph[u][j] < dist[j]) {

                    dist[j] = dist[u] + graph[u][j];
                }
            }
        }

        printDistances(dist);
    }

    public static int minDistance(int[] dist, boolean[] visited) {

        int min = Integer.MAX_VALUE;
        int minIndex = -1;

        for (int i = 0; i < dist.length; i++) {

            if (!visited[i] && dist[i] <= min) {

                min = dist[i];
                minIndex = i;
            }
        }

        return minIndex;
    }

    public static void printDistances(int[] dist) {

        System.out.println("Vertex \t Distance from Source");
        
        for (int i = 0; i < dist.length; i++) {
            System.out.println(i + " \t " + dist[i]);
        }
    }
}

其中 `graph` 为邻接矩阵，`source` 表示起点。运行后输出各个顶点到起点的最短距离。