迪杰斯特拉求单源最短路径Java

迪杰斯特拉算法用于求解有权图的单源最短路径问题，下面是Java代码实现：

import java.util.Arrays;

public class Dijkstra {
    private static final int INF = Integer.MAX_VALUE;  // 无穷大

    public void dijkstra(int[][] graph, int src) {
        int n = graph.length;
        int[] dist = new int[n];     // 存储最短距离
        boolean[] visited = new boolean[n];    // 标记节点是否已访问

        Arrays.fill(dist, INF);     // 初始化为无穷大
        dist[src] = 0;              // 设置源节点到自己的距离为0

        for (int i = 0; i < n - 1; i++) {
            // 选择距离最短的节点
            int u = minDistance(dist, visited);
            visited[u] = true;

            // 更新相邻节点的最短距离
            for (int v = 0; v < n; v++) {
                if (!visited[v] && graph[u][v] != 0 && dist[u] != INF && dist[u] + graph[u][v] < dist[v]) {
                    dist[v] = dist[u] + graph[u][v];
                }
            }
        }

        // 输出最短距离
        for (int i = 0; i < n; i++) {
            System.out.println("源节点到 " + i + " 的最短距离为：" + dist[i]);
        }
    }

    private int minDistance(int[] dist, boolean[] visited) {
        int min = INF, 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 main(String[] args) {
        int[][] graph = {{0, 3, 2, 0, 0},
                         {3, 0, 0, 5, 0},
                         {2, 0, 0, 1, 6},
                         {0, 5, 1, 0, 4},
                         {0, 0, 6, 4, 0}};

        Dijkstra obj = new Dijkstra();
        obj.dijkstra(graph, 0);
    }
}