算法之Dijkstra算法：最短路径探索的智慧之光

紫风

发布于 2025-10-14 15:14:00

1100

代码可运行

运行总次数：0

代码可运行

一、算法本质

Dijkstra算法如同一位智慧的导航员：

逐步探索：从起点出发，逐步确认到各节点的最短路径（贪心策略）
最优选择：每次选择当前已知最短路径的节点进行扩展
动态更新：根据新发现的路径不断优化距离估计

整个过程就像在迷雾中点亮一盏盏路灯，逐步照亮整个地图的最短路径。

二、Java实现（优先队列优化版）

import java.util.*;

class Graph {
    private int V;
    private List<List<Node>> adj;

    class Node implements Comparable<Node> {
        int vertex;
        int distance;

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

        @Override
        public int compareTo(Node other) {
            return Integer.compare(this.distance, other.distance);
        }
    }

    public Graph(int V) {
        this.V = V;
        adj = new ArrayList<>();
        for (int i = 0; i < V; i++) {
            adj.add(new ArrayList<>());
        }
    }

    public void addEdge(int src, int dest, int weight) {
        adj.get(src).add(new Node(dest, weight));
        // 无向图需添加反向边：adj.get(dest).add(new Node(src, weight));
    }

    public int[] dijkstra(int src) {
        int[] dist = new int[V];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[src] = 0;

        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(src, 0));

        boolean[] visited = new boolean[V];

        while (!pq.isEmpty()) {
            Node node = pq.poll();
            int u = node.vertex;

            if (visited[u]) continue;
            visited[u] = true;

            for (Node neighbor : adj.get(u)) {
                int v = neighbor.vertex;
                int weight = neighbor.distance;
                
                if (dist[v] > dist[u] + weight) {
                    dist[v] = dist[u] + weight;
                    pq.add(new Node(v, dist[v]));
                }
            }
        }
        return dist;
    }

    public static void main(String[] args) {
        Graph g = new Graph(5);
        g.addEdge(0, 1, 4);
        g.addEdge(0, 2, 1);
        g.addEdge(2, 1, 2);
        g.addEdge(2, 3, 5);
        g.addEdge(1, 3, 1);
        g.addEdge(3, 4, 3);

        int[] dist = g.dijkstra(0);
        System.out.println("从0出发到各顶点的最短距离：");
        for (int i = 0; i < dist.length; i++) {
            System.out.println(i + " : " + dist[i]);
        }
    }
}

三、性能分析

指标	数值	说明
时间复杂度	O((V+E) log V)	使用优先队列优化（V:顶点，E:边）
空间复杂度	O(V+E)	存储邻接表和优先队列
最佳场景	无负权边的加权图	适用于大多数现实场景

算法特性：

保证找到非负权图中的单源最短路径
使用优先队列（堆）优化搜索效率
无法处理负权边（需使用Bellman-Ford算法）

四、应用场景

地图导航：城市道路最短路径规划
网络路由：IP数据包传输路径选择
物流调度：仓库到配送点的最优路线
游戏AI：NPC智能寻路系统
电路设计：最小延迟信号传输路径

典型案例：

Google Maps路径规划引擎
亚马逊物流配送路线优化
《魔兽世界》NPC移动算法
5G网络流量调度系统

五、学习路线

新手必练：

手工推演算法过程（纸笔绘制步骤）
实现不同图结构的版本（邻接矩阵/邻接表）
可视化算法执行过程（推荐VisuAlgo网站）

// 邻接矩阵实现示例
public void dijkstraMatrix(int[][] graph, int src) {
    int V = graph.length;
    int[] dist = new int[V];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[src] = 0;
    
    boolean[] visited = new boolean[V];
    
    for (int count = 0; count < V-1; count++) {
        int u = minDistance(dist, visited);
        visited[u] = true;
        
        for (int v = 0; v < V; v++) {
            if (!visited[v] && graph[u][v] != 0 && 
                dist[u] != Integer.MAX_VALUE &&
                dist[u] + graph[u][v] < dist[v]) {
                dist[v] = dist[u] + graph[u][v];
            }
        }
    }
}

高手进阶：

实现双向Dijkstra搜索（起点和终点同时搜索）
开发分布式版本（处理超大规模图）
结合A*算法启发式搜索

// 双向Dijkstra核心逻辑
public int bidirectionalDijkstra(Graph graph, int src, int dest) {
    // 初始化前向和后向搜索
    PriorityQueue<Node> frontQueue = new PriorityQueue<>();
    PriorityQueue<Node> backQueue = new PriorityQueue<>();
    
    int[] frontDist = new int[V];
    int[] backDist = new int[V];
    Arrays.fill(frontDist, Integer.MAX_VALUE);
    Arrays.fill(backDist, Integer.MAX_VALUE);
    
    frontDist[src] = 0;
    backDist[dest] = 0;
    
    while (!frontQueue.isEmpty() && !backQueue.isEmpty()) {
        // 交替执行前向和后向搜索
        expandFrontier(frontQueue, frontDist);
        expandFrontier(backQueue, backDist);
        
        // 检查相遇节点
        int meetNode = checkMeetingPoint(frontDist, backDist);
        if (meetNode != -1) {
            return frontDist[meetNode] + backDist[meetNode];
        }
    }
    return -1; // 无通路
}