Dijkstra算法详解（Java语言实现最短路径查找）

算法核心思想

Dijkstra算法采用贪心策略，每一步都选择当前距离起点最近的未访问节点，并用它来更新其邻居节点的距离。整个过程可以分为以下几个步骤：

1. 初始化：将起点距离设为0，其他所有点设为无穷大（表示尚未到达）。
2. 创建一个优先队列（或最小堆），按当前已知最短距离排序。
3. 从队列中取出距离最小的节点，标记为已访问。
4. 遍历该节点的所有邻居，尝试通过当前节点找到更短的路径。
5. 重复上述过程，直到所有节点都被访问。

Java实现Dijkstra算法

下面我们使用Java编写一个完整的Dijkstra算法实现。我们将使用邻接表来表示图，并借助PriorityQueue（优先队列）来高效地获取当前最短距离的节点。

import java.util.*;// 表示图中的边class Edge {    int target;    int weight;        public Edge(int target, int weight) {        this.target = target;        this.weight = weight;    }}public class DijkstraAlgorithm {        // 使用邻接表存储图    private List<List<Edge>> graph;    private int vertices;        public DijkstraAlgorithm(int vertices) {        this.vertices = vertices;        graph = new ArrayList<>(vertices);        for (int i = 0; i < vertices; i++) {            graph.add(new ArrayList<>());        }    }        // 添加一条有向边    public void addEdge(int source, int target, int weight) {        graph.get(source).add(new Edge(target, weight));    }        // Dijkstra算法主函数    public void dijkstra(int start) {        // 距离数组，dist[i] 表示从起点到 i 的最短距离        int[] dist = new int[vertices];        Arrays.fill(dist, Integer.MAX_VALUE);        dist[start] = 0;                // 优先队列：按距离从小到大排序        PriorityQueue<Edge> pq = new PriorityQueue<>((a, b) -> a.weight - b.weight);        pq.offer(new Edge(start, 0));                // 记录已访问的节点        boolean[] visited = new boolean[vertices];                while (!pq.isEmpty()) {            Edge current = pq.poll();            int u = current.target;                        if (visited[u]) continue;            visited[u] = true;                        // 遍历所有邻居            for (Edge edge : graph.get(u)) {                int v = edge.target;                int weight = edge.weight;                                // 如果找到更短路径，则更新                if (!visited[v] && dist[u] != Integer.MAX_VALUE &&                     dist[u] + weight < dist[v]) {                    dist[v] = dist[u] + weight;                    pq.offer(new Edge(v, dist[v]));                }            }        }                // 输出结果        System.out.println("从节点 " + start + " 到各节点的最短距离：");        for (int i = 0; i < vertices; i++) {            if (dist[i] == Integer.MAX_VALUE) {                System.out.println("到节点 " + i + ": 不可达");            } else {                System.out.println("到节点 " + i + ": " + dist[i]);            }        }    }        // 测试示例    public static void main(String[] args) {        DijkstraAlgorithm g = new DijkstraAlgorithm(6);        g.addEdge(0, 1, 4);        g.addEdge(0, 2, 2);        g.addEdge(1, 2, 1);        g.addEdge(1, 3, 5);        g.addEdge(2, 3, 8);        g.addEdge(2, 4, 10);        g.addEdge(3, 4, 2);        g.addEdge(3, 5, 6);        g.addEdge(4, 5, 3);                g.dijkstra(0);    }}

代码说明

上面的代码实现了完整的Dijkstra算法。其中：

• Edge 类用于表示图中的边，包含目标节点和权重。
• DijkstraAlgorithm 类使用邻接表存储图结构。
• dijkstra 方法是算法的核心，使用优先队列优化性能。
• 在 main 方法中，我们构建了一个测试图并调用算法。

时间复杂度与适用场景

使用优先队列实现的Dijkstra算法时间复杂度为 O((V + E) log V)，其中 V 是顶点数，E 是边数。该算法广泛应用于路由协议、地图导航、网络优化等领域。

需要注意的是，Dijkstra算法不能处理负权边。如果图中存在负权边，应考虑使用 Bellman-Ford 算法。

总结

通过本教程，你已经掌握了如何用Java实现Dijkstra算法，理解了其工作原理和应用场景。无论是学习图论算法，还是准备面试，掌握这一经典算法都至关重要。希望这篇教程能帮助你打下坚实的算法基础！

关键词：Dijkstra算法、最短路径算法、Java实现Dijkstra、图论算法