Dijkstra算法 java

Dijkstra算法是一种用于解决单源最短路径问题的算法，它可以求解各个节点到达源点的最短路径或权值。在Java中，可以通过以下步骤实现Dijkstra算法：

1. 创建一个图的表示，包括节点和边的信息。
2. 初始化距离数组，用于记录每个节点到源点的最短距离。
3. 创建一个优先队列，用于选择下一个要访问的节点。
4. 将源点添加到优先队列中，并将其距离设置为0。
5. 循环执行以下步骤，直到优先队列为空：
- 从优先队列中取出距离最小的节点。
- 遍历该节点的所有邻居节点，更新它们的最短距离。
- 如果更新后的最短距离小于原来的距离，则将该节点添加到优先队列中。
6. 最终，距离数组中存储的就是每个节点到源点的最短距离。

以下是一个使用Java实现Dijkstra算法的示例代码[^1]：

import java.util.*;

public class DijkstraAlgorithm {
    public static void dijkstra(int[][] graph, int source) {
        int n = graph.length;
        int[] distance = new int[n];
        boolean[] visited = new boolean[n];
        Arrays.fill(distance, Integer.MAX_VALUE);
        distance[source] = 0;

        PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.comparingInt(node -> distance[node]));

        pq.offer(source);

        while (!pq.isEmpty()) {
            int node = pq.poll();
            visited[node] = true;

            for (int i = 0; i < n; i++) {
                if (graph[node][i] != 0 && !visited[i]) {
                    int newDistance = distance[node] + graph[node][i];
                    if (newDistance < distance[i]) {
                        distance[i] = newDistance;
                        pq.offer(i);
                    }
                }
            }
        }

        // 输出最短距离
        for (int i = 0; i < n; i++) {
            System.out.println("Node " + i + ": " + distance[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(graph, 0);
    }
}

这段代码实现了Dijkstra算法，通过传入一个邻接矩阵表示的图和源点的索引，计算出每个节点到源点的最短距离。在示例中，我们使用了一个9个节点的图，并输出了每个节点到源点的最短距离。