Dijkstra算法——java实现

Dijkstra算法是一种用于在加权图中找到最短路径的算法，它可以处理没有负权边的图。算法的基本思想是，从源点开始，逐步增加到其他顶点的距离，直到找到最短路径为止。Dijkstra算法采用贪心策略，每次找到距离源点最近的一个未被访问的顶点，并更新其他顶点到源点的距离。

在Java中实现Dijkstra算法通常需要使用优先队列来优化查找当前距离源点最近顶点的过程。以下是Dijkstra算法的Java实现的一个简单例子：

import java.util.*;

class Dijkstra {
    // 图的顶点数量
    private static final int N = 9;

    // Dijkstra算法的实现
    public static void dijkstra(int[][] graph, int startVertex) {
        // 记录源点到每个顶点的最短路径
        int[] dist = new int[N];
        // 初始化距离数组，所有顶点距离设置为无穷大
        Arrays.fill(dist, Integer.MAX_VALUE);
        // 用于标记顶点是否被访问过
        boolean[] visited = new boolean[N];

        // 起始点到自身的距离是0
        dist[startVertex] = 0;

        // 用优先队列优化查找最小距离的顶点
        PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.comparingInt(i -> dist[i]));

        // 将起始点加入优先队列
        pq.add(startVertex);

        while (!pq.isEmpty()) {
            // 从优先队列中选出距离最小的顶点
            int u = pq.poll();

            // 如果这个顶点已经被访问过，跳过
            if (visited[u]) continue;
            // 标记顶点为已访问
            visited[u] = true;

            // 遍历所有邻接的顶点
            for (int v = 0; v < N; v++) {
                // 如果顶点u到顶点v存在边，并且顶点v未被访问
                if (graph[u][v] != 0 && !visited[v]) {
                    // 计算源点通过顶点u到顶点v的路径长度
                    int newDist = dist[u] + graph[u][v];

                    // 如果新的路径长度小于当前记录的路径长度，则更新之
                    if (newDist < dist[v]) {
                        dist[v] = newDist;
                        // 将顶点v加入优先队列
                        pq.add(v);
                    }
                }
            }
        }

        // 输出从源点到每个顶点的最短路径长度
        for (int i = 0; i < N; i++) {
            System.out.println("Distance from vertex " + startVertex + " to vertex " + 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}
        };

        // 从顶点0开始计算最短路径
        dijkstra(graph, 0);
    }
}

在这个例子中，`graph`是一个图的邻接矩阵表示，`dijkstra`方法实现了Dijkstra算法，`main`方法用于测试算法。请注意，这个例子假设图是用邻接矩阵表示的，并且顶点编号从0开始。