Problem of The Day: Path with Maximum Probability

Problem Statement

Intuition

When I first approached this problem, my thought was to find the maximum probability path from the start node to the end node. This is quite similar to finding the shortest path in a graph, but instead of summing distances, I need to multiply probabilities. The idea of using Dijkstra’s algorithm came to mind since it is well-suited for problems involving path optimization.

Approach

My approach involves using a variation of Dijkstra’s algorithm. Instead of minimizing the path cost, I maximize the probability. I maintain a max-heap to always explore the path with the highest probability next. For each node, I calculate the potential new probability if I were to travel to a neighboring node. If this new probability is greater than the current stored probability for that neighbor, I update it and push this new probability onto the heap.

Complexity

• Time complexity: The time complexity of this approach is (O(E \log V)), where (E) is the number of edges, and (V) is the number of vertices. This is because we process each edge and maintain a heap of vertices.
• Space complexity: The space complexity is (O(V + E)) because we store the graph as an adjacency list and maintain a priority queue and an array for probabilities.

Code

import heapq
from collections import defaultdict
from typing import List

class Solution:
    def dijkstra(self, graph, start, end, n):
        probabilities = [float('-inf')] * n
        max_heap = [(-1, start)]
        probabilities[start] = 0
        while max_heap:
            prob, node = heapq.heappop(max_heap)
            if node == end:
                return -prob
            for nei, curr_prob in graph[node]:
                new_prob = -curr_prob * prob
                if new_prob > probabilities[nei]:
                    probabilities[nei] = new_prob
                    heapq.heappush(max_heap, (-new_prob, nei))
        return 0

    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)):
            a, b = edges[i]
            prob = succProb[i]
            graph[a].append([b, prob])
            graph[b].append([a, prob])

        return self.dijkstra(graph, start_node, end_node, n)

Editorial

Approach 1: Bellman-Ford Algorithm

class Solution:
    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start: int, end: int) -> float:
        max_prob = [0] * n
        max_prob[start] = 1

        for i in range(n - 1):
            # If there is no larger probability found during an entire round of updates,
            # stop the update process.
            has_update = 0
            for j in range(len(edges)):
                u, v = edges[j]
                path_prob = succProb[j]
                if max_prob[u] * path_prob > max_prob[v]:
                    max_prob[v] = max_prob[u] * path_prob
                    has_update = 1
                if max_prob[v] * path_prob > max_prob[u]:
                    max_prob[u] = max_prob[v] * path_prob
                    has_update = 1
            if not has_update:
                break

        return max_prob[end]

Approach 2: Shortest Path Faster Algorithm

class Solution:
    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start: int, end: int) -> float:
        graph = defaultdict(list)
        for i, (a, b) in enumerate(edges):
            graph[a].append([b, succProb[i]])
            graph[b].append([a, succProb[i]])

        max_prob = [0.0] * n
        max_prob[start] = 1.0

        queue = deque([start])
        while queue:
            cur_node = queue.popleft()
            for nxt_node, path_prob in graph[cur_node]:

                # Only update max_prob[nxt_node] if the current path increases
                # the probability of reach nxt_node.
                if max_prob[cur_node] * path_prob > max_prob[nxt_node]:
                    max_prob[nxt_node] = max_prob[cur_node] * path_prob
                    queue.append(nxt_node)

        return max_prob[end]

Approach 3: Dijkstra’s Algorithm

class Solution:
    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start: int, end: int) -> float:
        graph = defaultdict(list)
        for i, (u, v) in enumerate(edges):
            graph[u].append((v, succProb[i]))
            graph[v].append((u, succProb[i]))

        max_prob = [0.0] * n
        max_prob[start] = 1.0

        pq = [(-1.0, start)]
        while pq:
            cur_prob, cur_node = heapq.heappop(pq)
            if cur_node == end:
                return -cur_prob
            for nxt_node, path_prob in graph[cur_node]:

                if -cur_prob * path_prob > max_prob[nxt_node]:
                    max_prob[nxt_node] = -cur_prob * path_prob
                    heapq.heappush(pq, (-max_prob[nxt_node], nxt_node))
        return 0.0