Abstract / Summary

Find the path between two nodes in a graph that has the highest probability of being traversed.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 55% (200k+ submissions).

Typical patterns to solve this problem:

• Array
• Graph
• Heap (Priority Queue)
• Shortest Path

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation solves the problem of finding the maximum success probability of a path between two nodes in an undirected weighted graph. Each edge carries a probability value, and the probability of a path is the product of the probabilities of its constituent edges. The algorithm explores the graph using a priority-driven search that always expands the currently most promising node, guaranteeing that the first time the destination node is removed from the queue the optimal probability has been found.

Building the adjacency structure

The first logical block creates a convenient representation of the graph. A defaultdict of lists stores, for every vertex, the pairs (probability, neighbor). The construction iterates over the parallel collections edges and succProb, pairing each edge with its associated probability.

neighbors = defaultdict(list)
for (a, b), p in zip(edges, succProb):
    neighbors[a].append((p, b))
    neighbors[b].append((p, a))

By inserting entries for both directions, the structure captures the undirected nature of the graph without requiring additional logic later in the traversal.

Preparing the search structures

Two auxiliary containers are prepared before the main loop.

A set named done records vertices whose best probability has already been fixed, preventing redundant work.

A list todo is initialized with a single tuple (-1, start_node). The negative sign converts the default min-heap provided by heapq into a max-heap, because the algorithm always wants to pop the node with the highest accumulated probability.

done = set()
todo = [(-1, start_node)]   # max-heap via negative probabilities

Main exploration loop

The core of the algorithm is a while loop that continues until the priority queue is empty. In each iteration the node with the largest current probability is extracted.

while todo:
    p, node = heappop(todo)
    if node == end_node:
        return -p
    if node in done:
        continue
    done.add(node)
    ...

The early-return when node equals end_node implements an immediate termination condition: because nodes are processed in decreasing order of probability, the first time the destination appears guarantees the maximal achievable product.

The done check eliminates any stale entries that may have been inserted earlier with inferior probabilities. Once a node is marked as completed, any later occurrence of that node in the heap is ignored.

Expanding neighbors

For each neighbor of the current node, a new candidate probability is computed by multiplying the current accumulated probability p (still negative) with the edge’s success probability success. The resulting product remains negative, preserving the max-heap invariant. The neighbor together with its new probability is then pushed onto the heap.

for success, next in neighbors[node]:
    heappush(todo, (p * success, next))

Because the heap stores the negative of the true probability, the multiplication p * success correctly updates the sign and magnitude.

Edge-case handling

The algorithm gracefully handles several special situations without extra code.

When the start node is identical to the end node, the initial heap entry contains the start node with probability -1. The first pop immediately satisfies the node == end_node condition, and the function returns 1.0 (the negated value of -1). This correctly reflects the fact that a zero-length path has probability one.

If the graph contains isolated vertices or vertices that are unreachable from the start, the heap will eventually become empty. The final return 0 statement yields a probability of zero, indicating that no path exists.

Edges with a probability of zero are still inserted into the adjacency list. When such an edge is traversed, the product p * 0 becomes zero, and the resulting entry placed on the heap carries a probability of zero. Since the heap always extracts the largest (least negative) value first, any zero-probability paths will be considered only after all positive-probability alternatives have been exhausted, ensuring they never incorrectly dominate a valid solution.

The use of a set for done also prevents infinite loops in the presence of cycles, because each vertex is processed at most once.

Performance optimizations

Several design choices contribute to efficient execution.

The adjacency list built with defaultdict(list) provides O(1) average-time insertion and lookup for neighbor collections, enabling rapid iteration over incident edges.

Transforming the min-heap into a max-heap by storing negative probabilities avoids the need for a custom comparator, leveraging the highly optimized heapq implementation.

The early exit upon reaching the destination eliminates unnecessary exploration of the remaining graph, which can be substantial in dense or large instances.

Marking vertices as completed in the done set ensures that each vertex’s outgoing edges are examined at most once, preventing repeated work caused by multiple heap entries for the same node.

Finally, the algorithm avoids any explicit recursion or auxiliary data structures beyond the heap and the visited set, keeping the memory footprint modest relative to the size of the input graph.

Imagine you are looking for the best way to travel through a magical forest. Each path between the trees has a special number that shows how likely you are to make it through, like paths that stay dry or paths that get muddy.

The computer starts by creating a map of all these connections. It looks at every path and writes down which trees are connected and how likely you are to succeed on each one.

Next, a special bag is used to keep track of the places you can go. This bag is very smart because it always keeps the easiest, most successful path right at the top so it is the first one pulled out.

The computer picks the best path in the bag and checks where it leads. If that spot is the one being searched for, the goal is reached. If not, paths to new trees are added into the bag, always multiplying the chances so the computer keeps track of the total success all the way from the start.

Some places might be visited more than once by different paths, so the computer keeps a list of places already finished to make sure time is not wasted going over the same spot again. This continues until the very best way to reach the final tree is found.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: loglinear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Java		Python			TS
	WalkCCC	C++	Java		Python
	leetcode.ca	C++	Java		Python		Go	TS
	Progiez	C++	Java		Python
github	black-shadows	C++
	charles-wangkai		Java
	everthis			JS
	FelixFan1122		Java
	fsq	C++
	JoshCrozier			JS
	keineahnung2345	C++
	lkwq007				Python
	MacJim	C++
	suxrobGM					C#
	varunu28		Java
	wisdompeak	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
FelixFan1122	Java
fsq	C++
JoshCrozier	JavaScript
keineahnung2345	C++
lkwq007	Python
MacJim	C++
suxrobGM	C#
varunu28	Java
wisdompeak	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality