1514. Path with Maximum Probability

https://leetcode.com/problems/path-with-maximum-probability/

You are given an undirected weighted graph of n nodes (0-indexed), represented by an edge list where edges[i] = [a, b] is an undirected edge connecting the nodes a and b with a probability of success of traversing that edge succProb[i].

Given two nodes start and end, find the path with the maximum probability of success to go from start to end and return its success probability.

If there is no path from start to end, return 0. Your answer will be accepted if it differs from the correct answer by at most 1e-5.

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 != end

• 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.

单源无向图每条边附有概率，从起点到终点最大概率是多少。是单源最短路径的反问题，将最短替换成最长。无负权值 + 单源最短路径=>Dijkstra算法，贪心思想。每次从已访问过的结点中选择距离最长的结点cur，遍历cur的邻居且如果从cur到邻居nei的距离大于已存的到nei的距离，则更新到nei的距离并将更新过的距离重新放入已访问过的集合中。集合中选最大用max heap。

from heapq import heappush, heappop

class Solution:
    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start: int, end: int) -> float:
        p, g = [0.0] * n, collections.defaultdict(list)
        for i, (a, b) in enumerate(edges):
            g[a].append((b, succProb[i]))
            g[b].append((a, succProb[i]))
        p[start] = 1
        heap = [(-p[start], start)]
        while heap:
            prob, cur = heappop(heap)
            if cur == end: return -prob
            for nei, e_prob in g[cur]:
                cand_prob = -prob * e_prob
                if cand_prob > p[nei]:
                    p[nei] = cand_prob
                    heappush(heap, (-p[nei], nei))
        return 0