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

Approach 01:

class Solution {
public:
    double maxProbability(int numNodes, vector<vector<int>>& edges, vector<double>& successProbabilities, int startNode, int endNode) {
        vector<vector<pair<int, double>>> graph(numNodes);
        priority_queue<pair<double, int>> maxHeap;
        maxHeap.emplace(1.0, startNode);
        vector<bool> visited(numNodes);

        for (int i = 0; i < edges.size(); ++i) {
            const int nodeA = edges[i][0];
            const int nodeB = edges[i][1];
            const double probability = successProbabilities[i];
            graph[nodeA].emplace_back(nodeB, probability);
            graph[nodeB].emplace_back(nodeA, probability);
        }

        while (!maxHeap.empty()) {
            const auto [currentProbability, currentNode] = maxHeap.top();
            maxHeap.pop();
            if (currentNode == endNode) {
                return currentProbability;
            }
            if (visited[currentNode]) {
                continue;
            }
            visited[currentNode] = true;
            for (const auto& [adjacentNode, edgeProbability] : graph[currentNode]) {
                if (visited[adjacentNode]) {
                    continue;
                }
                maxHeap.emplace(currentProbability * edgeProbability, adjacentNode);
            }
        }

        return 0;
    }
};

import heapq
from typing import List

class Solution:
    def maxProbability(self, numNodes: int, edges: List[List[int]], successProbabilities: List[float], startNode: int, endNode: int) -> float:
        graph = [[] for _ in range(numNodes)]
        maxHeap = [(-1.0, startNode)]
        visited = [False] * numNodes

        for i in range(len(edges)):
            nodeA = edges[i][0]
            nodeB = edges[i][1]
            probability = successProbabilities[i]
            graph[nodeA].append((nodeB, probability))
            graph[nodeB].append((nodeA, probability))

        while maxHeap:
            currentProbability, currentNode = heapq.heappop(maxHeap)
            currentProbability = -currentProbability
            if currentNode == endNode:
                return currentProbability
            if visited[currentNode]:
                continue
            visited[currentNode] = True
            for adjacentNode, edgeProbability in graph[currentNode]:
                if not visited[adjacentNode]:
                    heapq.heappush(maxHeap, (-(currentProbability * edgeProbability), adjacentNode))

        return 0

Time Complexity

• Graph Construction:

  Constructing the graph takes \( O(\text{numEdges}) \) time since we iterate over each edge and add it to the adjacency list.

• Dijkstra’s Algorithm with Max-Heap:

  In the worst case, we will process each node and each edge. The max-heap operations (push and pop) each take \( O(\log \text{numNodes}) \) time. Therefore, the time complexity of this part is \( O((\text{numNodes} + \text{numEdges}) \log \text{numNodes}) \).

• Overall Time Complexity:

  The overall time complexity is \( O((\text{numNodes} + \text{numEdges}) \log \text{numNodes}) \).

Space Complexity

• Graph Storage:

  The adjacency list for the graph requires \( O(\text{numNodes} + \text{numEdges}) \) space, where each node’s adjacency list stores its edges.

• Max-Heap:

  The max-heap can hold up to \( O(\text{numNodes}) \) elements in the worst case.

• Visited Array:

  The visited array requires \( O(\text{numNodes}) \) space to keep track of visited nodes.

• Overall Space Complexity:

  The overall space complexity is \( O(\text{numNodes} + \text{numEdges}) \), dominated by the adjacency list storage.