这周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 凑个五题完成这篇文章
有写错或写得不清楚的地方还请你版大老斧正 不胜感激