Path with Maximum Probability

How it works

SPFA is an optimization of Bellman-Ford that uses a queue to process only nodes whose distances (or probabilities) have changed. Instead of iterating through all edges in every round, we only process edges from nodes that might lead to improvements. This can be significantly faster in practice, especially for sparse graphs.

Steps

1. Build an adjacency list and initialize maxProb array with maxProb[start] = 1.0.
2. Use a queue and add the start node. Maintain a boolean array to track which nodes are currently in the queue.
3. While the queue is not empty, dequeue a node and mark it as no longer in the queue.
4. For each neighbor, compute the new probability. If it improves the neighbor's best probability, update it.
5. If the neighbor is not already in the queue, add it and mark it as in the queue.
6. Return maxProb[end_node].

Complexity

• Time complexity: O(V * E)
• Space complexity: O(V + E)

Where V is the number nodes and E is the number of edges.

Things to watch for

Using Min-Heap Instead of Max-Heap

Unlike shortest path problems where we minimize distance, this problem requires maximizing probability. Using a min-heap (the default in most languages) will process low-probability paths first, leading to incorrect results or inefficiency. Always use a max-heap or negate the probabilities when using a min-heap.

In Rust, be careful when using to_bits() as a heap key. Storing Reverse((-prob).to_bits()) does not order probabilities like a numeric max-heap, and can pop a lower probability before a higher one. Since probabilities are non-negative, storing prob.to_bits() in a BinaryHeap preserves the needed order.

Reversing the Stale-State Check

When using a maxProb array, a heap entry is stale only when its probability is lower than the best probability already recorded for that node. The check should be curr_prob < maxProb[node], not curr_prob > maxProb[node].

Initializing Start Probability to Zero

The starting node should have a probability of 1.0 (certainty), not 0.0. Multiplying any edge probability by zero will always yield zero, preventing the algorithm from finding any valid path. Initialize maxProb[start_node] = 1.0 before beginning the search.

Forgetting the Graph is Undirected

Each edge connects two nodes bidirectionally, so you must add both directions to the adjacency list. Forgetting to add the reverse edge means some paths will be unreachable, potentially missing the optimal solution or returning zero when a valid path exists.

from typing import List
from collections import deque

class Solution:
    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start_node: int, end_node: int) -> float:
        adj = [[] for _ in range(n)]
        for i in range(len(edges)):
            src, dst = edges[i]
            adj[src].append((dst, succProb[i]))
            adj[dst].append((src, succProb[i]))

        maxProb = [0.0] * n
        maxProb[start_node] = 1.0
        q = deque([start_node])

        while q:
            node = q.popleft()

            for nei, edge_prob in adj[node]:
                new_prob = maxProb[node] * edge_prob
                if new_prob > maxProb[nei]:
                    maxProb[nei] = new_prob
                    q.append(nei)

        return maxProb[end_node]

class Solution {
public:
    double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb, int start_node, int end_node) {
        vector<vector<pair<int, double>>> adj(n);

        for (int i = 0; i < edges.size(); i++) {
            int src = edges[i][0], dst = edges[i][1];
            adj[src].emplace_back(dst, succProb[i]);
            adj[dst].emplace_back(src, succProb[i]);
        }

        vector<double> maxProb(n, 0.0);
        maxProb[start_node] = 1.0;
        queue<int> q;
        q.push(start_node);

        while (!q.empty()) {
            int node = q.front();
            q.pop();

            for (auto& [nei, edgeProb] : adj[node]) {
                double newProb = maxProb[node] * edgeProb;
                if (newProb > maxProb[nei]) {
                    maxProb[nei] = newProb;
                    q.push(nei);
                }
            }
        }

        return maxProb[end_node];
    }
};