---
# System prepended metadata

title: Python-LeetCode 581 第12招 Shortest Path
tags: [LeetCode, python]

---

# Python-LeetCode 581 第12招 Shortest Path

我們前面介紹了無加權圖上面以BFS計算最短距離的方法，對於DAG我們也可以沿著拓樸順序來計算距離，但是應用問題中，更常見的是邊上有加權也可能有環路的圖。Dijkstra演算法是用在一個加權圖上計算一點到所有點的最短路徑的演算法，圖可以是有向的或無向的，但是邊上的權重必須是非負的。

## 基本原理

假設輸入的圖是$G=(V,E,w)$與一個起點，我們要計算起點到每一點的一條最短路徑。我們以下面的題目來說明Dijkstra的運作原理與程式寫法。

[(題目連結) 743. Network Delay Time (Medium)](https://leetcode.com/problems/network-delay-time/)
這題是單一起點到所有點的最短路徑裸題。給定一個有向圖與指定起點，要求出起點$k$到每一點的最短路徑長度，輸出最遠一點的距離。

先揭示範例程式，再來解釋其中的原理與技巧。

```python=
class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        adj = [[] for i in range(n+1)]
        for u,v,w in times:
            adj[u].append((v,w))
        oo = 10000
        d = [oo]*(n+1)
        d[k] = 0
        pq = [(0,k)] # min-heap (d[v],v)
        while pq:
            dist,u = heapq.heappop(pq)
            if dist > d[u]: continue
            for v,w in adj[u]:
                if d[v] > d[u]+w:
                    d[v] = d[u]+w
                    heapq.heappush(pq,(d[v],v))
        imax = max(d[1:])
        if imax==oo: return -1
        return imax 

```
首先，對於輸入資料我們需要做一個轉換。通常輸入給的是邊的集合，以本題來說times: List[List[int]]是輸入邊的集合，每一個邊$(u,v,w)$表示點$u$到點$v$有一條邊長度是$w$。演算法運過程中，我們需要的是每一個點有哪些走出去的邊。因此我們對每一點$u$建立一個list，每個元素$(v,w)$代表一個$u$點走到$v$的邊長度$w$。(第 3 ~ 5行)

演算法運作過程中，用兩個容器維護兩個迴圈不變性：
* 對每一點$v$，以$d[v]$紀錄**目前已知**起點$k$到$v$的最短距離。如果尚未發現任何路徑就以一個不可能的大的值oo表示。
* 容器pq儲存最短距離尚未確定的點。它是一個min-heap，所以每個儲存的點$v$以$(d[v],v)$的形式存在pq中，也就是以目前的$v$點目前的最短路徑長度為key值。

演算法原理其實不困難，我們重複執行下面兩點，直到pq中沒有點為止。
* 每次在尚未確定距離的點中，找出$d[]$最小的$u$，因為邊長都不是負的，所以$d[u]$的值不可能更短了，我們就知道$u$點的最短路徑是確定的了。因此，可以將$u$點從pq中刪除。
* 然後，用$d[u]$去嘗試更新與$u$相鄰的$v$點的距離。若有一個邊$(u,v,w)$，那麼，有一條起點到$u$再走到$v$的路長度是$d[u]+w$，如果這個值比原來存的$d[v]$小，要更新$d[v]$的值。

要做出$O(n^2)$複雜度的Dijkstra演算法一點都不困難，例如在dense graph上以鄰接矩陣儲存時，我們直接不需要使用min-heap當容器，依照上述兩點來寫，就可以了。

要把時間複雜度降下來，最重要的是每一回合如何很快地找到$d[]$最小的點，這就是我們使用資料結構min-heap幫忙的原因，因為每次找到一點之後，我們會更新其他點的$d[]$，因此$d[]$是會動態變化的，也就是說無法靠著一開始用排序來處理。

但是這裡的困難還不只在於此，最大的問題在於每一回合可能有某些$d[]$值會更動(降低)。基本上PQ是以heap寫的，如果是自己寫的heap，我們可以修改這個資料結構，讓它可以處理decreasing key的狀況，但是解題時為了節省時間，我們會採用Python提供的PQ，而此PQ並不提供降key的功能，多數競賽選手採取的變通方法是以下”偷懶”的策略：

我們將$(d[u],u)$放在$pq$中，當我們要將$d[u]$修改為$x$的時候，我們並不從$pq$中刪除或更新該筆資料，而是直接將$(x,u)$再加入$pq$中。這樣一來，對於某些點，$pq$中可能會有多筆資料，但是無論如何，最小的會先出來，因為我們只做decreasing key，所以最先出來的是最新的資料。需要額外處理的事情是，當我們每一回合找最小值時，需要檢查出來最小值的點是否已經處理完畢了，如果是，則直接丟掉它。

我們看範例程式。重點在第10行開始的while迴圈，每一回合會pop出最小值(第11行)，也就是確定一點$u$的最短距離，但是在第12行我們會檢查出來的點是否已經出來過了，如果$pq$中彈出的$dist > d[u]$就表示這次彈出的剩餘無用的殘骸，則直接不予理會，否則，出來的才是我們要的。第13行的for迴圈，我們檢查該點的鄰居，如果有更好的$d[]$值就予以更新，如同前面說的，我們將更新後的直接壓入$pq$中。

時間複雜度是多少呢？若圖有$m$個邊$n$個點，因為每個點的鄰居數總和是$m$，而在PQ上的操作都在$O(\log n)$時間內，所以總時間是$O(m\log n)$。
(本單元中將以$m$表示邊數而$n$表示點數。)

補充說明：如果圖中有些點是從起點走不到的，最後找出來的距離就是初設的無窮大。此外，最後$d[v]$是最短距離，那麼要如何找路徑呢？我們可以對每一點$v$存一個$parent[v]$，它是$v$點最短路徑的前一點，我們在每次找到更好的路徑要更新距離時，也更新$parent[v]$。當計算完成時，由後往前一步一步回推就可以得到路徑經過的點的順序。名字取為$parent$的原因是：如果將每個點與它的$parent$連起來，我們會得到一棵以起點為根的樹狀圖，這個樹稱為shortest-path tree，在此樹上，起點到任一點的路徑都是在原圖上的最短路徑。

## 範例題


[(題目連結) 787. Cheapest Flights Within K Stops (Medium)](https://leetcode.com/problems/cheapest-flights-within-k-stops/)
題目有一點變化。給一個有向圖，要求起點到終點的最短路徑，但中間節點不得超過$k$個，也就是最多只能走$k+1$個邊。

我們可以走一個BFS的方式來控制紀錄所走的邊數，因為經過的邊數多不一定距離(本題的價錢)長，所以走過的點仍然要考慮。
以下是範例程式。我們用一個$que$來存尚待檢查的點，每一個元素包含$(cost,step,vertex)$。$step$初值給$-1$，所以最多只能到$k$就不能在往下走(第13行)。如果邊數尚未超過，就檢查後面可以接的點，嘗試更新更小的成本(第14 ~ 18行)。因為任一點被檢查成本時的$step$值是非遞減的，所以我們只需要處理更小的成本就好，對於$step$變大而$cost$也變大的狀況，我們可以丟棄不理。

時間複雜度$O(kn+km)$，因為每個點最多進入$que$中$k$次，所以邊被檢查的總次數也是$km$。 
```python=
class Solution:
    # BFS with step limit
    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
        adj = [[] for i in range(n)]
        for s,t,p in flights:
            adj[s].append((t,p))
        mincost = [1000000]*n
        que = [(0,-1,src)] # cost, step, vertex
        head = 0
        while head<len(que):
            cost,step,v = que[head]
            head += 1
            if step>=k: continue
            for u,price in adj[v]:
                p = cost+price
                if p<mincost[u]:
                    mincost[u] = p
                    que.append((p,step+1,u))
        #end while
        if mincost[dst]==1000000:
            return -1
        return mincost[dst] 
```

[(題目連結) 882. Reachable Nodes In Subdivided Graph (Hard)](https://leetcode.com/problems/reachable-nodes-in-subdivided-graph/)
Subdivide一根edge是指將一根邊上面塞入若干點，新加入的點都是degree=2，也就是把一根edge變成一條沒有岔路的path。這題是說給一個無向圖的起點(0號點)與一個距離限制$maxMoves$，此外也指定每個邊上要subdivide加入的點數後，請問有多少個點是可以走到的，包含原來的點與subdivide增加的點。

以下圖為例，行走距離的限制$maxMoves=6$，$(0,1)$這條邊上要插入10點、$(0,2)$插入1點以及$(2,1)$要插入2點。形成的graph如右圖，最後能走到的點數是13點(黃色部分)。
![](https://hackmd.io/_uploads/SyJggL8Wa.png)

其實一根邊上要加入的點數$c$可以看成邊的長度是$c+1$，我們計算起點到所有原始點的最短路徑長，就知道每一個原始點是否能走得到。至於新插入的點，我們可以算有多少走不到，然後用總數去減就是走得到的點。
因此，我們每到達一點，就對它連接的邊做計算，假設走到$v$點的距離是$d$，對連接的邊$(v,x)$，我們就將這個邊所不能走到的點數減去$maxMoves - d$。因為一個邊恰有兩端點，兩端點會對同一個邊各做一次，所以最後邊上走不到的點數就會被正確的算出，例外的情形是兩邊會重複算或者扣超過(例如只有3個點卻減5)，這個狀況就是邊上沒有走不到的點，我們可以在最後拋棄所有的負值就行了。

以下是範例程式。我們用$visit$來表示一個點是否已經確定最短路徑長，$pq$中則放入尚未確定點的距離值與點編號。$unreach$是一個字典Counter，用來記錄每一個邊上走不到的點數。$total$則是所有邊上subdivide的總點數。因為輸入邊保證編號前小後大，所以$unreach$將來用前小後大的tuple來表示。第4 ~ 14行是初值設定與輸入轉換。

第15行開始跑一個while，進入後，從$pq$彈出最小值，第17行檢查如果已經超過距離限制，就離開結束while。第18行檢查，這是否是這個點第一次離開$pq$，若否，則是$pq$殘留的，不予理會。
第20行對每一個鄰接的邊，要扣除$unreach$的點數，但記得我們字典的key要前小後大，所以第21 ~ 22行用一個 if 來做，此外，將邊所連接的下一點$u$放入$pq$中。
最後，答案是能走到的原始點加上subdivide點，原始點就用$visit[]$來判斷，新插入點就用$total$扣掉走不到的點數。
時間複雜度與Dijkstra一樣是$O(m\log n)$。

```python=
class Solution:
    # dijkstra
    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:
        visit = [False]*n
        oo = 1000000001
        adj = [[] for i in range(n)]
        unreach = Counter()
        total = 0
        for u,v,c in edges:
            adj[u].append((v,c))
            adj[v].append((u,c))
            unreach[u,v] = c
            total += c
        pq = [(0,0)] #(d[v],v)
        while pq:
            d,v = heapq.heappop(pq) # ensure d<=maxMoves
            if d>maxMoves: break
            if visit[v]: continue # duplicate
            visit[v] = True
            for u,c in adj[v]:
                if u<v: unreach[u,v] -= maxMoves - d
                else: unreach[v,u] -= maxMoves - d
                heapq.heappush(pq,(d+c+1,u)) # maybe duplicate
            #end for
        #end file
        return sum(visit)+total-sum(max(0,x) for x in unreach.values())

```

[(題目連結) 1976. Number of Ways to Arrive at Destination (Medium)](https://leetcode.com/problems/number-of-ways-to-arrive-at-destination/)
給一個無向圖，邊上有正的權值。請計算點$0$到$n-1$有幾條最短路徑。

在一個有向或無向圖上，要找出$s$到$t$的所有最短路徑是一個基本圖論的問題。我們可以先觀察到以下的事實：**所有$s$到$t$的最短路徑會形成一個DAG，在這個DAG上的所有路徑就是所有$s$到$t$的最短路徑**。假設$d_s(v)$與$d_t(v)$分別是點$v$在圖上到$s$與$t$的距離。則
* $d_s(v)+d_t(v)=d_s(t)$若且為若$v$點在這個DAG上。
* 對在此DAG上的點$v$與$u$，若存在邊$(v,u,w)$且$d_s(v)+w=d_s(u)$，則有一條最短路徑經過$(v,u,w)$這條邊，也就是這條邊在此DAG上。

對於一個單一起點單一終點的DAG，其路徑數是個簡單DP。令$p[v]$為走到$v$的路徑數，則
$$
p[v] = \sum_{(u,v)\in DAG}p[u]
$$

這一題我們可以用以下的步驟來做：
1. 以Dijkstra算出$d_s(v)$
2. 以Dijkstra算出$d_t(v)$
3. 找出DAG上的所有點，並依據起點的距離排序(是一個topological sort)
4. 根據此序列走訪計算路徑數。

以下是範例程式。第4 ~ 16行是標準的輸入轉換與Dijkstra，不須再多做說明，但這個副程式會將算出的距離從$dist$中傳回。
第18 ~ 21行靠呼叫dijk來算出$ds$與$dt$。
第23行抓出DAG中所有的點，並在第25行根據$ds$排序。第24行是把這些點放入一個集合以便查詢。
接著根據此順序進行走訪並計算路徑數。

時間複雜度$O((m+n)\log n)$。 
```python=
class Solution:
    # dijkstra + dag
    def countPaths(self, n: int, roads: List[List[int]]) -> int:
        oo = 10**12
        adj = [[] for i in range(n)]
        for u,v,w in roads:
            adj[u].append((v,w)); adj[v].append((u,w))
        def dijk(source,dist):
            pq = [(0,source)] # (delta,v)
            while pq:
                delta,v = heappop(pq)
                if delta != dist[v]: continue #useless
                for u,w in adj[v]:
                    if delta+w<dist[u]:
                        dist[u]=delta+w
                        heappush(pq,(dist[u],u))
        # dijk 
        ds = [oo]*n; ds[0] = 0
        dijk(0,ds)
        dt = [oo]*n; dt[n-1]=0
        dijk(n-1,dt)
        # traverse the shortest path dag, sort by distance
        s = [i for i in range(n) if ds[i]+dt[i]==ds[n-1]]
        dag = set(s)
        s.sort(key=lambda x:ds[x]) # 
        p = [0]*n # num of path
        p[0] = 1
        for v in s:
            for u,w in adj[v]:
                if u in dag and ds[u]==ds[v]+w:
                    p[u] += p[v]
        return p[n-1]%1000000007
                     
```
**Another Solution**
計算shortest path的數量也可直接修改Dijkstra演算法，同時計算路徑長度與最短路徑數，以下是這樣的範例程式。
主要的修改在於：
* 除了存距離的$d$之外，再多一個存數量的$num$；
* 當$v$點從PQ中彈出距離確定時，我們要更新其他點$u$的最短路徑長，如果找到更短的路徑，除了更新距離外，也設定數量(第15 ~ 18行)；
* 多增加一個條件，當找到與目前最短路徑相同長度時，更新它的數量(第19 ~ 20行)。

時間複雜度也是與Dijkstra相同。

```python=
class Solution:
    # one-pass dijkstra for length and num of path 
    def countPaths(self, n: int, roads: List[List[int]]) -> int:
        oo = 10**12
        adj = [[] for i in range(n)]
        for u,v,w in roads:
            adj[u].append((v,w)); adj[v].append((u,w))
        d,num = [oo]*n,[0]*n
        d[0] = 0; num[0] = 1 # num of shortest path
        pq = [(0,0)] # (delta,v)
        while pq:
            delta,v = heappop(pq)
            if delta != d[v]: continue #useless
            for u,w in adj[v]:
                if delta+w < d[u]:
                    d[u] = delta+w
                    num[u] = num[v]
                    heappush(pq,(d[u],u))
                elif delta+w == d[u]: # another path to u
                    num[u] += num[v]
        return num[n-1]%1000000007
                     

```

[(題目連結) 2045. Second Minimum Time to Reach Destination (Hard)](https://leetcode.com/problems/second-minimum-time-to-reach-destination/description/)
題目有一點複雜。給一個雙向圖，也就是無向圖，通過每個邊需要花費的時間是一樣的(某個給定的正整數$time$)，每個點上都有一個紅綠燈，所有點的紅綠燈是同步的，每隔$change$的時間紅綠切換一次，一開始的時候所有點都是綠燈。紅燈時不可通行，綠燈時不可等待，必須立刻進入某個鄰接的邊。求起點(1)出發到達終點($n$)的第二小時間。所謂第二小是必須嚴格大於最小值，不可相等。

這相當於找第二短路徑，但此處路徑的定義不要求是simple path(點邊不得重複的路徑)，點邊可以重複的路徑也稱為walk。如果是simple path這題目就非常的困難了，walk就沒這麼困難了。

在Dijkstra算法中，我們對每個點找最短路徑長，一旦找到最短路徑，這個點就當作訪問過，不必再理會它。我們可以很自然地擴展延伸這個算法來找第二短的walk，每個點都記錄最小與第二小的路徑長。

至於紅綠燈的問題，並不難處理，因為所有紅綠燈都是同步的，對於時間$t$，若$t\%(2\times change)<change$就無需等待，否則需要等待$2\times change - t\%(2\times change)$的時間。

以下是範例程式，我們說明與標準Dijkstra差異之處即可。第9行的距離$d$每個點都會有兩個值：$d[0]$最小是，$d[1]$是次小。
初始時只有起點的最小值是0，其他都是oo。$pq$內放的是(距離,點編號)。進入while迴圈後，每次彈出最小距離$dist$與該點編號$v$，如果$dist$比$v$的第二小距離還大，就是無用的殘留物，不予理會(第14行)。第15 ~ 17行計算等待時間與到達下一點的時間，對於鄰接點$u$，如果是等於最小值(重複)或者大於等於$u$的第二小值，都是無用的，否則都是有用的，如果是最小值就更新最小與次小；如果是次小就更新次小，有用的就要放進$pq$中來更新後面的點。

時間複雜度與Dijkstra是一樣的$O((m+n)\log n)$，因為每個點最多只有兩次出$pq$時需要更新其他點，所以更新的次數不會超過$2m$。 
```python=
class Solution:
    def secondMinimum(self, n: int, edges: List[List[int]], time: int, change: int) -> int:
        adj = [[] for i in range(n+1)]
        for u,v in edges:
            adj[u].append(v)
            adj[v].append(u)
        oo = 10**9
        change2 = change+change
        d = [[oo,oo] for i in range(n+1)]
        d[1][0] = 0
        pq = [(0,1)] # (distance,vertex)
        while pq and d[n][1]==oo:
            dist, v = heappop(pq)
            if dist>d[v][1]: continue # useless
            tt = dist%change2
            if tt>=change: dist += change2-tt # wait for green
            dist += time # time to arrival next vertex
            for u in adj[v]:
                if dist == d[u][0] or dist>=d[u][1]: continue
                if dist<d[u][0]: d[u] = [dist,d[u][0]]
                else: d[u][1] = dist
                heappush(pq,(dist,u))
            #print(v,d)
        # end while
        return d[n][1] 

```

[(題目連結) 2203. Minimum Weighted Subgraph With the Required Paths (Hard)](https://leetcode.com/problems/minimum-weighted-subgraph-with-the-required-paths/)
給一個有向圖邊上有正的權值(長度)，另外給兩個起點$src1,src2$與一個終點$dest$。要找權重總和最小的子圖(邊的子集合)，滿足在此子圖上兩個起點都走得到終點。

題目的要求等價於**存在一點$v$，兩個起點都能到達$v$，而$v$能到達終點**。$v$點可能是起點或終點中的一點。理解這一點之後，答案就是
$$
\min_v \{d(src1,v)+d(src2,v)+d(v,dest)\}
$$

我們可以做3次Dijkstra，兩次分別求$src1$與$src2$到所有點的距離，第3次求所有點到$dest$的距離，這個可以將邊逆向後計算。最後在計算目標函數的值。
以下是範例程式。在轉換輸入邊時，用2個adjacency list存順向鄰居與逆向鄰居。Dijkstra的副程式稍做修改將算出來的距離可以透過參數回傳。時間複雜度還是與Dijkstra一樣的$O((m+n)\log n)$。 
```python=
class Solution:
    # min{d(s1,v)+d(s2,v)+d(v,t)}
    def minimumWeight(self, n: int, edges: List[List[int]], src1: int, src2: int, dest: int) -> int:
        oo = 10**10+1
        def dijk(s,adj,d): # compute s to all distance
            d[s] = 0
            pq = [(0,s)]
            while pq:
                dist,v = heappop(pq)
                if dist > d[v]: continue
                for u,r in adj[v]:
                    if d[v]+r<d[u]:
                        d[u]=d[v]+r
                        heappush(pq,(d[u],u))
        #end dijk
        adj1 = [[] for i in range(n)] # forward edge
        adj2 = [[] for i in range(n)] # backward edge
        for u,v,w in edges:
            adj1[u].append((v,w))
            adj2[v].append((u,w))
        ds1,ds2,dt = [oo]*n,[oo]*n,[oo]*n
        dijk(src1,adj1,ds1)
        dijk(src2,adj1,ds2)
        dijk(dest,adj2,dt)
        ans = min(ds1[v]+ds2[v]+dt[v] for v in range(n))
        if ans>=oo: return -1
        return ans

```



## 結語

Shortest path其實是個很重要也很常遇到的問題。除了BFS求無權圖最短路徑、DAG上的最長或最短路徑外，本單元Dijkstra算法是用來求邊上權值是非負時的最短路徑。此外Tree上的路徑可以看成DAG來做。
Dijkstra演算法理論上最好的時間複雜度是$O(m+n\log n)$，這個需要特殊的資料結構來支援，一般解題時用的都是$O((m+n)\log n)$，兩者相差很有限。

常用的最短路徑演算法還有Bellman-Ford algorithm，用來求有負邊的狀況下的最短路徑，以及Floyd-Warshall algorithm，用來算all-to-all shortest paths。Floyd-Warshall雖然時間複雜度不如把Dijkstra跑$n$次，但他的推導過程是個很漂亮的DP，結果是非常簡潔的漂亮演算法，而且實際跑起來很快。
LeetCode中Shortest path的題目並不多，而且大部分只需要BFS或DAG或Dijkstra就夠了。根據筆者的觀察，LeetCode比較不喜歡出特殊演算法的題目，而喜歡的是**眾所周知的演算法**的變化與 **演算法策略**的應用(如Greedy, DP等)。這應該跟網站的目的在模擬面試有關，這是與競程不太一樣的地方。


