這周leetcode圖周 剛好把之前不會的地方補上
之後應該會寫union Find吧
Dijkstra演算法其實就求一點到任意點的最短路徑
圖可以是有向圖也可以是無向圖
但權值必須非負值
遇到題目的步驟如下:
1.將邊轉換成無向圖或有向圖 graph
2.開一個紀錄各點最短路徑的list result，並更新起點的值
3.開一個heap pq，更新各點的最短路徑，並保證每次跳出來的是該節點的最短路徑
藉此增進演算法效率
4.將起點的權值跟起點放入heap，heap會以起點的權值做排序(註1)
5.heap為空前，重複執行以下幾點:
(1)heap彈出node跟node的權值，假如node == 目標 回傳result[node]
(2)遍歷graph[node]，你會得到另一點 neighber與node到neighber的權值
(3)將node權值與neighber做運算 得到新的距離 假如此新距離 < result[neighber]
紀錄的最短距離 更新result[neighber]並將新的最短距離與neighber放入heap
題目:
https://leetcode.com/problems/path-with-maximum-probability
1514. Path with Maximum Probability
給定一無向圖，圖上有權值，權值代表成功走到該點的機率
給定起點與終點 請回傳走到終點的最大機率
Example 1:
Input: n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.2], start =
0, end = 2
Output: 0.25000
Explanation: There are two paths from start to end, one having a probability
of success = 0.2 and the other has 0.5 * 0.5 = 0.25.
Example 2:
Input: n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.3], start =
0, end = 2
Output: 0.30000
Example 3:
Input: n = 3, edges = [[0,1]], succProb = [0.5], start = 0, end = 2
Output: 0.00000
Explanation: There is no path between 0 and 2.
Constraints:
2 <= n <= 10^4
0 <= start, end < n
start !0 <= a, b < n
a != b
0 <= succProb.length == edges.length <= 2*10^4
0 <= succProb[i] <= 1
There is at most one edge between every two nodes.
思路:
照著上面步驟 首先把edges與對應的succProb轉成無向圖
開一個長度n的list 紀錄最大機率
開一個heap並把start與start的值放入
因為這邊求最大機率 我們需要大堆頂 所以值要加負號
然後照上面步驟開迴圈
走到end 回傳result[node]
遍歷graph[node] 計算新的機率 假如新的機率比result紀錄的機率大
我們就更新result[node] 並且把新機率與node放入heap
Python Code:
class Solution:
def maxProbability(self, n: int, edges: List[List[int]], succProb:
List[float], start_node: int, end_node: int) -> float:
graph = defaultdict(list)
for i in range(len(edges)):
graph[edges[i][0]].append((edges[i][1], succProb[i]))
graph[edges[i][1]].append((edges[i][0], succProb[i]))
result = [0] * n
result[start_node] = 1
pq = [(-1, start_node)]
while pq:
curr_prob, node = heapq.heappop(pq)
curr_prob = -curr_prob
if node == end_node:
return curr_prob
for neighbor, prob in graph[node]:
new_prob = curr_prob * prob
if new_prob > result[neighbor]:
result[neighbor] = new_prob
heapq.heappush(pq, (-new_prob, neighbor))
return 0.0
題目2:
https://leetcode.com/problems/number-of-ways-to-arrive-at-destination
1976. Number of Ways to Arrive at Destination
給定一無向圖 邊上有正的權值 請計算0到n-1總共有幾條最短路徑
思路:
稍微變化的題目
我們還是能依照上面的步驟 只是需要多加個list紀錄最短路徑數量 count
先做無向圖 做result紀錄最短路徑 做heap 然後開兩個迴圈
因為這邊是求最短路徑
所以我們使用小堆頂即可 路徑的權值就不用加負號
假如迴圈裡面遇到更小的最短路徑 除了要更新result 還要更新count
遇到新的最短路徑 == result[node] 我們就將count[neighber] += count[node]
Python Code:
class Solution:
def countPaths(self, n: int, roads: List[List[int]]) -> int:
graph = defaultdict(list)
for r in roads:
graph[r[0]].append((r[1],r[2]))
graph[r[1]].append((r[0],r[2]))
result = [float("inf") for _ in range(n)]
result[0] = 0
count = [0 for _ in range(n)]
count[0] = 1
pq = [(0,0)]
while pq:
cur_value, node = heapq.heappop(pq)
if node == n-1:
return count[node] % (10 ** 9 + 7)
for neighbor, value in graph[node]:
new_value = cur_value + value
if new_value < result[neighbor]:
result[neighbor] = new_value
count[neighbor] = count[node]
heapq.heappush(pq,(new_value,neighbor))
elif result[neighbor] == new_value:
count[neighbor] += count[node]
return 0
註1:python內建heap是小堆頂 如果需要記錄最大值 請記得將權值加上負號
取出後再把它變會正的
明天再做個三題Dijkstra 湊個五題完成這篇文章
有寫錯或寫得不清楚的地方還請你版大老斧正 不勝感激