1514. Path with Maximum Probability

Option 1: Dijkstra's algorithm

cost of an edge is abs diff between 2 nodes
cost of an path is max cost of edges in the path (instead of total cost of edges)

class Solution:
    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start: int, end: int) -> float:
        graph = {node: [] for node in range(n)}
        for i, edge in enumerate(edges):
            graph[edge[0]].append((edge[1], succProb[i]))
            graph[edge[1]].append((edge[0], succProb[i]))
        
        pq = [(-1, start)]
        probs = [0] * n
        
        while pq:
            prob, cur = heapq.heappop(pq)
            if cur == end:
                return -prob
            for next_node, sp in graph[cur]:
                new_prob = -prob * sp
                if new_prob > probs[next_node]:
                    probs[next_node] = new_prob
                    heapq.heappush(pq, (-new_prob, next_node))
        
        return 0

Option 2: Union find

UF works because the cost of a path is the max cost of edges in the path

Option 3: Binary search + dfs/bfs The complexity of this approach is fine since the search space is small (ie, 10^6 at most so log 10^6 is small)

1514. Path with Maximum Probability - cocoder39/coco39_LC GitHub Wiki