Path with Maximum Probability

Leetcode Problem 1514: Path with Maximum Probability

Problem Summary

You are given an undirected weighted graph of n nodes where each edge has an associated probability of success. Given a start node and an end node, find the path with the maximum probability of success from start to end. The probability of a path is the product of the probabilities of all its edges. If no path exists, return 0. The graph can have up to 10,000 nodes and up to 20,000 edges. Edge probabilities range from 0 to 1, and there is at most one edge between every two nodes. The answer is accepted if it differs from the correct answer by at most 1e-5.

Techniques

Array
Graph Theory
Heap (Priority Queue)
Shortest Path

Solution

import { Heap } from "../heap";

type Edge = { node: number; cost: number };
type HeapNode = { node: number; cost: number };

/// this version of dijkstra's algorithm is for maximization problems, instead of minimization problems.
/// it tries to find the path with the maximum product of edge weights, instead of the path with the minimum sum of edge weights.
function dijkstraMaximixation(
    n: number,
    graph: Edge[][],
    start: number
): number[] {
    const dist: number[] = Array(n).fill(0);
    dist[start] = 1;

    const maxCostHeap = new Heap<HeapNode>((a, b) => b.cost - a.cost);
    maxCostHeap.insert({ node: start, cost: 1 });

    while (maxCostHeap.size() > 0) {
        const current = maxCostHeap.extract()!;
        const { node, cost } = current;

        if (cost < dist[node]) { 
            continue;
        }

        for (const { node: next, cost: weight } of graph[node]) {
            const newCost = cost * weight;

            if (newCost > dist[next]) {
                dist[next] = newCost;
                maxCostHeap.insert({ node: next, cost: newCost });
            }
        }
    }

    return dist;
}

function createUndirectedGraph(edges: number[][], succProb: number[], n: number) { 
    const graph: Edge[][] =  Array.from({ length: n }, () => []);

    for (let i = 0; i < edges.length; i++) {
        const [u, v] = edges[i]
        const cost = succProb[i]
        graph[u].push({ node: v, cost }); 
        graph[v].push({ node: u, cost });
    }

    return graph;
}

function maxProbability(n: number, edges: number[][], succProb: number[], start_node: number, end_node: number): number {
    const graph = createUndirectedGraph(edges, succProb, n)
    const distances = dijkstraMaximixation(n, graph, start_node)
    return distances[end_node]
};

console.log(maxProbability(3, [[0,1],[1,2],[0,2]], [0.5,0.5,0.2], 0, 2)); // 0.25
console.log(maxProbability(3, [[0,1],[1,2],[0,2]], [0.5,0.5,0.3], 0, 2)); // 0.3
console.log(maxProbability(3, [[0,1]], [0.5], 0, 2)); // 0