Find the Most Reliable Path Through a Network

Problem Statement

You are given an undirected graph representing a computer network with n nodes labeled from 0 to n - 1. The network topology is defined by a list of edges, where each edge is specified as [u, v, prob], indicating a bidirectional connection between node u and node v with a transmission success probability of prob (0.0 <= prob <= 1.0).

The reliability (success probability) of a path is defined as the product of the success probabilities of all edges along that path. If a path contains no edges (e.g., from a node to itself), its probability is 1.0.

Write a function max_probability(n: int, edges: list[list[float]], start_node: int, end_node: int) -> float that returns the maximum probability of successfully sending a packet from start_node to end_node. If no path exists between start_node and end_node, return 0.0.

Your solution should properly handle parallel edges (multiple edges between the same pair of nodes), cycles, links with zero probability, and disconnected components.

Function Signature

def max_probability(n: int, edges: list[list[float]], start_node: int, end_node: int) -> float:
    pass

Constraints

• 1 <= n <= 10^5
• 0 <= len(edges) <= 2 * 10^5
• Each edge is a list [u, v, prob] where 0 <= u, v < n and 0.0 <= prob <= 1.0
• 0 <= start_node, end_node < n
• Parallel edges and self-loops may be present.
• Results within 1e-5 of the actual answer will be accepted.

Examples

Example 1

Input: n = 3, edges = [[0, 1, 0.5], [1, 2, 0.5], [0, 2, 0.2]], start_node = 0, end_node = 2
Output: 0.25
Explanation:
Path 0 -> 2 has probability 0.2.
Path 0 -> 1 -> 2 has probability 0.5 * 0.5 = 0.25.
The maximum probability is 0.25.

Example 2

Input: n = 4, edges = [[0, 1, 0.8], [1, 2, 0.5], [2, 3, 0.0]], start_node = 0, end_node = 3
Output: 0.0
Explanation:
Any path reaching node 3 must pass through the edge with probability 0.0, resulting in a total path probability of 0.0.

Example 3

Input: n = 3, edges = [[0, 1, 0.4]], start_node = 0, end_node = 2
Output: 0.0
Explanation: Node 2 is not reachable from node 0.