什么是Dijkstra算法？

Dijkstra算法是用來尋找最短路徑最著名的算法之一。具體來說，Dijkstra算法主要用來尋找一個邊的權(quán)值不為負(fù)的有向圖中的任意一點到其他任意結(jié)點（在兩點相互聯(lián)通的情況下）之間的最小路徑。如果利用Dijkstra算法找出從一點出發(fā)，到圖中其他所有點的最短路徑，事實上我們就構(gòu)造出了一個最短路徑樹（shortest-path tree）。

Dijkstra最短路徑算法因其簡單高效的特征而被廣泛應(yīng)用于互聯(lián)網(wǎng)的路由協(xié)議中，例如IS-IS（Intermediate System to Intermediate System）和OSPF（Open Shortest Path First）協(xié)議。

Dijkstra算法的歷史

1956年，當(dāng)Edsger W. Dijkstra在阿姆斯特丹數(shù)學(xué)中心（Mathematical Center in Amsterdam）工作室，為了說明一臺名為ARMAC的新電腦的計算能力，發(fā)明了最小路徑問題。Dijkstra期初的目的是提出一個能被非計算機(jī)背景的人所能理解的問題，同時這一問題能被計算機(jī)有效解決。因此他對荷蘭64個城市簡化過的交通圖（之所以是64個城市，是為了使得6比特的內(nèi)存能夠完全編碼這些城市）計算最短路徑，同時實現(xiàn)了Dijkstra算法的最初版本。

算法

Dijkstra算法實際上是一個貪婪算法（Greedy algorithm）。因為該算法總是試圖優(yōu)先訪問每一步循環(huán)中距離起始點最近的下一個結(jié)點。Dijkstra算法的過程如下圖所示。

Dijkstra Animation

下面我們分別給出算法的步驟及其正確性的證明。

初始化

1. 給定圖中的一個結(jié)點s作為起始點。
2. 給定一個數(shù)組dist[]存儲圖中所有結(jié)點到s的距離。將dist[s]初始化為0。對于圖中的其他結(jié)點v，初始化dist[v]為無窮大。初始化為無窮大的意義在于我們假設(shè)其余所有結(jié)點在當(dāng)前情況下尚未與s聯(lián)通。隨著算法的執(zhí)行，dist[v]會保存圖中從s到v的最短路徑的距離。
3. 給定一個minimum Heap，記為Q。堆頂為當(dāng)前情況下距離s最近的結(jié)點及相應(yīng)的距離。將(s, 0)放入堆中。
4. 給定一個Set，記為S，保存所有已經(jīng)訪問過的結(jié)點。Set初始為空?；贒ijkstra算法的性質(zhì)，我們總是以最短的路徑遍歷每一個結(jié)點，因此對于任一結(jié)點，一旦我們已經(jīng)訪問過，就代表著我們已經(jīng)得到了從s到達(dá)這一結(jié)點的最短路徑。

計算最短路徑

1. 當(dāng)Q不為空的情況下，取出堆頂?shù)脑?code>(v, [dist[v]) —— 也就是當(dāng)前距離s最近的結(jié)點v，及其距離dist[v]。
2. 如果v在S中，則代表我們已經(jīng)訪問過v的最短路徑。那么跳過當(dāng)前v，重復(fù)步驟1。
3. 否則，將v放在S中。
4. 對于每一個與v相鄰的結(jié)點t：
   • 如果dist[v] + weight(v, t) < dist[t]，則更新dist[t] = dist[v] + weight(v, t)。同時將(t, dist[t])放進(jìn)Q中。
   • 否則，不做任何處理。

當(dāng)算法結(jié)束后，dist[]中保存圖中每一個除s之外的結(jié)點到s的最短路徑的權(quán)重值（或長度）。如果從s到v不存在聯(lián)通的路徑，則dist[v] = ∞。

證明算法正確性

假設(shè)對于每個已經(jīng)訪問過的結(jié)點v，dist[v]存儲從起始點s到v的最短路徑。

當(dāng)算法初始化時，dist[]中只包含dist[s] = 0，其正確性顯而易見。

對于其余n-1個結(jié)點，假設(shè)u已經(jīng)被訪問且v尚未被訪問，同時u和v之間存在一條邊u -> v，其權(quán)重為weight(u,v)，那么一定有dist[v] = dist[u] + weight(u, v)。否則的話，假設(shè)存在另一條更短的路徑dist[t]滿足dist[t] + weight(t, v)，則根據(jù)上述算法，t一定先于u被訪問，則與我們當(dāng)前的假設(shè)產(chǎn)生了矛盾。該論斷對于余下的所有結(jié)點都成立。

因此Dijkstra算法一定能給出從出發(fā)點到其余所有結(jié)點（在可以到達(dá)的情況下）的最短路徑。

復(fù)雜度分析

設(shè)圖中總計有E條邊，N個結(jié)點。

時間復(fù)雜度：O(ElogE)。因為所使用的最小堆最大可達(dá)O(E)大小，同時我們從其中將每個元素取出來一次。

空間復(fù)雜度：O(N+E)。其中O(N)為存儲dist所用空間。O(E)為存儲圖的鄰接鏈表及最小堆所用空間。

Java實現(xiàn)

class DijkstraShortestPath {
    /**
     * Given a list of (source, target, weight) edge pairs, return the shortest distance from s to any
     * other nodes in the graph. Any unreachable node has a distance of Integer.MAX_VALUE. 
     * @param edges List of tuple representation of edges containing [source, target weight].
     * @param N The graph contains nodes from 1 to N. 
     * @param s Start node of the shortest path tree
     * @return Shortest path from s to other nodes in the graph.
     */
    public Map<Integer, Integer> dijkstraShortestPath(int[][] edges, int N, int s) {
        Map<Integer, List<int[]>> adjList = new HashMap<>();
        for (int[] edge : edges) {
            adjList.computeIfAbsent(edge[0], k -> new ArrayList<>()).add(new int[]{edge[1], edge[2]});
        }
        
        Map<Integer, Integer> dist = new HashMap<>();
        PriorityQueue<int[]> minHeap = new PriorityQueue<>((edge1, edge2) -> {
            return edge1[1] - edge2[1];
        });
        minHeap.offer(new int[]{s, 0});
        
        while (!minHeap.isEmpty()) {
            int[] curr = minHeap.poll();
            if (dist.containsKey(curr[0])) continue;
            dist.put(curr[0], curr[1]);
            if (adjList.containsKey(curr[0])) {
                for (int[] edge : adjList.get(curr[0])) {
                    minHeap.offer(new int[]{edge[0], edge[1] + curr[1]});
                }
            }
        }
        
        for (int i = 1; i <= N; i++) {
            if (!dist.containsKey(i)) {
                dist.put(i, Integer.MAX_VALUE);
            }
        }
        
        return dist;
    }
}