最短路径Dijkstra算法

一、问题定义

1.1 单源最短路径

给定带权有向图 ( G=(V, E) ) 和源点 ( s )，求 ( s ) 到所有其他顶点的最短路径。

1.2 前提条件

• 边权非负

二、核心思想

2.1 贪心策略

每次选择距离源点最近的未确定最短路径的顶点，其最短路径即确定。

2.2 松弛操作

if dist[u] + weight(u, v) < dist[v]:
    dist[v] = dist[u] + weight(u, v)

三、基本实现

3.1 邻接矩阵版 ( O(V^2) )

public int[] dijkstra(int[][] graph, int src) {
    int n = graph.length;
    int[] dist = new int[n];
    boolean[] visited = new boolean[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[src] = 0;
    
    for (int i = 0; i < n - 1; i++) {
        int u = -1;
        for (int j = 0; j < n; j++) {
            if (!visited[j] && (u == -1 || dist[j] < dist[u])) {
                u = j;
            }
        }
        visited[u] = true;
        
        for (int v = 0; v < n; v++) {
            if (!visited[v] && graph[u][v] != 0 && dist[u] != Integer.MAX_VALUE) {
                dist[v] = Math.min(dist[v], dist[u] + graph[u][v]);
            }
        }
    }
    return dist;
}

3.2 优先队列优化 ( O((V+E)\log V) )

public int[] dijkstraPQ(List<int[]>[] adj, int src) {
    int n = adj.length;
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[src] = 0;
    
    PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
    pq.offer(new int[]{src, 0});
    
    while (!pq.isEmpty()) {
        int[] curr = pq.poll();
        int u = curr[0], d = curr[1];
        
        if (d > dist[u]) continue;  // 已处理过更短路径
        
        for (int[] edge : adj[u]) {
            int v = edge[0], w = edge[1];
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.offer(new int[]{v, dist[v]});
            }
        }
    }
    return dist;
}

四、正确性证明

4.1 归纳法

归纳假设：已确定集合S中的顶点，其dist值已是最短路径。

归纳步骤：选择S外dist最小的顶点u，假设存在更短路径经过S外顶点x，则dist[x] < dist[u]，与u的选择矛盾。

五、对比

算法	适用	时间复杂度	特点
Dijkstra	非负权图	( O((V+E)\log V) )	单源，贪心
Bellman-Ford	含负权	( O(VE) )	可检测负环
Floyd	所有点对	( O(V^3) )	动态规划
SPFA	含负权	平均快，最坏 ( O(VE) )	Bellman-Ford优化

六、总结

Dijkstra算法是求解非负权图单源最短路径的经典算法。其核心是贪心选择 + 松弛操作。优先队列优化后，在稀疏图上效率很高，是实际应用中最常用的最短路径算法。