概率最大的路径 -- dijkstra算法应用

1514. 概率最大的路径

标准的Dijkstra 算法计算的是最短路径，计算的是最⼩值，这题让你计算最⼤概率是⼀个最⼤值，怎么可能⽤ Dijkstra 算法呢？

重点说说最⼤值和最⼩值这个问题，其实 Dijkstra 和很多最优化算法⼀样，计算的是「最优值」，这个最优值可能是最⼤值，也可能是最⼩值。
标准 Dijkstra 算法是计算最短路径的，但你有想过为什么 Dijkstra 算法不允许存在负权重边么？
因为 Dijkstra 计算最短路径的正确性依赖⼀个前提：路径中每增加⼀条边，路径的总权重就会增加。其实相当于求最小最大值，形如：$min(max(f(x)))$

如果你想计算最⻓路径【相当于本题的最大概率】，路径中每增加⼀条边，路径的总权重就会减少，要是能够满⾜这个条件，也可以⽤Dijkstra 算法。其实相当于求最大最小值，形如：$max(min(f(x)))$

只不过，这道题的解法要把优先级队列的排序顺序反过来，⼀些 if ⼤⼩判断也要反过来，见如下代码：

class Solution:

    class State:
        def __init__(self, id, distFromStart):
            """
            从start节点到当前节点的距离
            :param id:
            :param distFromStart:
            """
            self.id = id
            self.distFromStart = distFromStart

        # 优先级队列，大的先出列
        def __lt__(self, other):
            if self.distFromStart > other.distFromStart:
                return True
            return False

    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start_node: int, end_node: int) -> float:
        # 构图，⽆向图就是双向图
        graph = [[] for _ in range(n)]
        for i in range(len(edges)):
            src = edges[i][0]
            dst = edges[i][1]
            weight = succProb[i]
            graph[src].append([dst, weight])
            graph[dst].append([src, weight])

        # 定义：probTo[i] 的值就是节点 start 到达节点 i 的最⼤概率
        # 初始化为一个取不到的最小值，
        probTo = [-1] * len(graph)
        # base case
        probTo[start_node] = 1

        max_heap = []
        # 从起点s开始BFS
        heapq.heappush(max_heap, self.State(start_node, 1))

        while max_heap:
            curState = heapq.heappop(max_heap)
            curNodeID = curState.id
            curDistFromStart = curState.distFromStart

            # 如果只关心start 节点到某一个终点end的最短距离，此处加入一个判断即可
            if curNodeID == end_node:
                return curDistFromStart

            if curDistFromStart < probTo[curNodeID]:
                # 已经有一条更高概率的路径到达curNode节点了
                continue

            # 遍历curNodeID的相邻节点
            for neighbor in graph[curNodeID]:
                nextNodeID = neighbor[0]

                # 看看从 curNode 达到 nextNode 的概率是否会更⼤
                distToNextNode = curDistFromStart * neighbor[1]

                if distToNextNode > probTo[nextNodeID]:
                    # 更新dp table
                    probTo[nextNodeID] = distToNextNode
                    # 将该邻居节点加入优先级队列
                    heapq.heappush(max_heap, self.State(nextNodeID, distToNextNode))

        return 0.0


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68