Dijkstra 算法 (Dijkstra's Algorithm)

算法原理

Dijkstra算法用于在加权图中查找从单个源点到所有其他顶点的最短路径。该算法维护一个顶点集，这些顶点的最短路径已经确定。初始时，这个集合只包含源点。然后重复执行以下步骤：从尚未确定最短路径的顶点中选择一个距离最小的顶点，将其加入已确定最短路径的顶点集，并更新其所有未确定最短路径的邻居顶点的距离估计值。

算法步骤

1. 初始化：设置源点到自身的距离为0，到其他所有顶点的距离为无穷大
2. 创建一个优先队列，将所有顶点加入队列，优先级为当前已知的距离
3. 当优先队列不为空时，执行以下操作：
   • 从队列中取出距离最小的顶点u
   • 对于u的每个邻居v，检查是否可以通过u获得更短的路径到达v
   • 如果可以，则更新v的距离，并调整其在优先队列中的位置
4. 重复步骤3直到队列为空

代码实现

import java.util.*;

public class DijkstraAlgorithm {
    // 图的表示
    static class Graph {
        private int vertices;
        private List> adjList;
        
        static class Edge {
            int dest;
            int weight;
            
            Edge(int dest, int weight) {
                this.dest = dest;
                this.weight = weight;
            }
        }
        
        Graph(int vertices) {
            this.vertices = vertices;
            adjList = new ArrayList<>(vertices);
            for (int i = 0; i < vertices; i++) {
                adjList.add(new ArrayList<>());
            }
        }
        
        // 添加边
        void addEdge(int src, int dest, int weight) {
            adjList.get(src).add(new Edge(dest, weight));
        }
        
        // Dijkstra算法实现
        int[] dijkstra(int src) {
            // 距离数组，存储源点到各顶点的最短距离
            int[] dist = new int[vertices];
            // 访问标记数组
            boolean[] visited = new boolean[vertices];
            
            // 初始化距离数组
            Arrays.fill(dist, Integer.MAX_VALUE);
            dist[src] = 0;
            
            // 优先队列，按距离排序
            PriorityQueue pq = new PriorityQueue<>(vertices, new Node());
            
            pq.add(new Node(src, 0));
            
            while (!pq.isEmpty()) {
                // 取出距离最小的顶点
                int u = pq.poll().vertex;
                
                // 如果已访问过，则跳过
                if (visited[u]) continue;
                
                visited[u] = true;
                
                // 更新u的所有邻居的距离
                for (Edge edge : adjList.get(u)) {
                    int v = edge.dest;
                    int weight = edge.weight;
                    
                    // 如果通过u可以获得更短的路径，则更新距离
                    if (!visited[v] && dist[u] != Integer.MAX_VALUE && 
                        dist[u] + weight < dist[v]) {
                        dist[v] = dist[u] + weight;
                        pq.add(new Node(v, dist[v]));
                    }
                }
            }
            
            return dist;
        }
        
        // 节点类，用于优先队列
        static class Node implements Comparator {
            int vertex;
            int distance;
            
            Node() {}
            
            Node(int vertex, int distance) {
                this.vertex = vertex;
                this.distance = distance;
            }
            
            @Override
            public int compare(Node n1, Node n2) {
                return n1.distance - n2.distance;
            }
        }
    }

    // 测试方法
    public static void main(String[] args) {
        // 创建图
        Graph graph = new Graph(6);
        
        // 添加边 (起点, 终点, 权重)
        graph.addEdge(0, 1, 4);
        graph.addEdge(0, 2, 3);
        graph.addEdge(1, 2, 1);
        graph.addEdge(1, 3, 2);
        graph.addEdge(2, 3, 4);
        graph.addEdge(2, 4, 2);
        graph.addEdge(3, 4, 3);
        graph.addEdge(3, 5, 2);
        graph.addEdge(4, 5, 5);
        
        int source = 0;
        int[] distances = graph.dijkstra(source);
        
        System.out.println("从顶点 " + source + " 到各顶点的最短距离:");
        for (int i = 0; i < distances.length; i++) {
            if (distances[i] == Integer.MAX_VALUE) {
                System.out.println("到顶点 " + i + ": 无法到达");
            } else {
                System.out.println("到顶点 " + i + ": " + distances[i]);
            }
        }
    }
}

应用场景

• 路由算法：在网络路由中寻找最短路径
• 地图导航：计算两点之间的最短行驶距离
• 社交网络分析：寻找两个人之间的最短关系链
• 游戏开发：NPC寻路算法
• 交通规划：优化交通流量

优缺点