dijkstra java

Dijkstra算法是一种用于计算单源最短路径的经典算法，适用于带权有向图。该算法由荷兰计算机科学家Edsger W. Dijkstra于1956年提出。下面我将详细介绍Dijkstra算法的基础概念、优势、类型、应用场景以及在Java中的实现。

基础概念

Dijkstra算法的核心思想是通过逐步扩展已知最短路径的集合来找到从源节点到所有其他节点的最短路径。算法维护两个集合：一个包含已知最短路径的节点集合（通常称为visited），另一个包含尚未找到最短路径的节点集合（通常称为unvisited）。

优势

简单直观：算法逻辑清晰，易于理解和实现。
适用性广：适用于任何带权有向图，特别是权重非负的情况。
高效性：时间复杂度为O((V+E)logV)，其中V是顶点数，E是边数。

类型

Dijkstra算法有多种变体，主要区别在于如何选择下一个要处理的节点：

朴素Dijkstra算法：每次选择未访问节点中距离最小的节点。
优先队列优化Dijkstra算法：使用优先队列（如最小堆）来高效选择距离最小的节点。

应用场景

路由算法：在网络中找到最短路径。
GPS导航：计算两点之间的最短路线。
游戏AI：路径规划，使角色找到最短路径到达目标。

Java实现示例

以下是一个使用优先队列优化的Dijkstra算法的Java实现示例：

import java.util.*;

class Graph {
    private int vertices; // Number of vertices
    private LinkedList<Edge>[] adjacencyList; // Adjacency list

    Graph(int vertices) {
        this.vertices = vertices;
        adjacencyList = new LinkedList[vertices];
        for (int i = 0; i < vertices; i++) {
            adjacencyList[i] = new LinkedList<>();
        }
    }

    void addEdge(int source, int destination, int weight) {
        adjacencyList[source].add(new Edge(destination, weight));
        // For undirected graph, uncomment below line
        // adjacencyList[destination].add(new Edge(source, weight));
    }

    void dijkstra(int source) {
        int[] distances = new int[vertices]; // Array to store shortest distances from source
        Arrays.fill(distances, Integer.MAX_VALUE);
        distances[source] = 0;

        PriorityQueue<Node> priorityQueue = new PriorityQueue<>(vertices, Comparator.comparingInt(node -> node.distance));
        priorityQueue.add(new Node(source, 0));

        while (!priorityQueue.isEmpty()) {
            Node current = priorityQueue.poll();
            int u = current.vertex;

            for (Edge edge : adjacencyList[u]) {
                int v = edge.destination;
                int weight = edge.weight;

                if (distances[u] + weight < distances[v]) {
                    distances[v] = distances[u] + weight;
                    priorityQueue.add(new Node(v, distances[v]));
                }
            }
        }

        // Print shortest distances from source to all vertices
        System.out.println("Vertex Distance from Source");
        for (int i = 0; i < vertices; i++) {
            System.out.println(i + "\t\t" + distances[i]);
        }
    }

    class Edge {
        int destination, weight;
        Edge(int destination, int weight) {
            this.destination = destination;
            this.weight = weight;
        }
    }

    class Node {
        int vertex, distance;
        Node(int vertex, int distance) {
            this.vertex = vertex;
            this.distance = distance;
        }
    }

    public static void main(String[] args) {
        int vertices = 9;
        Graph graph = new Graph(vertices);
        graph.addEdge(0, 1, 4);
        graph.addEdge(0, 7, 8);
        graph.addEdge(1, 2, 8);
        graph.addEdge(1, 7, 11);
        graph.addEdge(2, 3, 7);
        graph.addEdge(2, 8, 2);
        graph.addEdge(2, 5, 4);
        graph.addEdge(3, 4, 9);
        graph.addEdge(3, 5, 14);
        graph.addEdge(4, 5, 10);
        graph.addEdge(5, 6, 2);
        graph.addEdge(6, 7, 1);
        graph.addEdge(6, 8, 6);
        graph.addEdge(7, 8, 7);

        graph.dijkstra(0);
    }
}