# 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點(黃色部分)。
其實一根邊上要加入的點數$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等)。這應該跟網站的目的在模擬面試有關，這是與競程不太一樣的地方。
Sign in with Wallet
Connect another wallet