> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/graph/1514.-path-with-maximum-probability.md).

# 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:**

![](https://assets.leetcode.com/uploads/2019/09/20/1558_ex1.png)

```
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:**

![](https://assets.leetcode.com/uploads/2019/09/20/1558_ex2.png)

```
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:**

![](https://assets.leetcode.com/uploads/2019/09/20/1558_ex3.png)

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

单源无向图每条边附有概率，从起点到终点最大概率是多少。是单源最短路径的反问题，将最短替换成最长。无负权值 + 单源最短路径=>Dijkstra算法，贪心思想。每次从已访问过的结点中选择距离最长的结点cur，遍历cur的邻居且如果从cur到邻居nei的距离大于已存的到nei的距离，则更新到nei的距离并将更新过的距离重新放入已访问过的集合中。集合中选最大用max heap。

```python
from heapq import heappush, heappop

class Solution:
    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start: int, end: int) -> float:
        p, g = [0.0] * n, collections.defaultdict(list)
        for i, (a, b) in enumerate(edges):
            g[a].append((b, succProb[i]))
            g[b].append((a, succProb[i]))
        p[start] = 1
        heap = [(-p[start], start)]
        while heap:
            prob, cur = heappop(heap)
            if cur == end: return -prob
            for nei, e_prob in g[cur]:
                cand_prob = -prob * e_prob
                if cand_prob > p[nei]:
                    p[nei] = cand_prob
                    heappush(heap, (-p[nei], nei))
        return 0
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://hao-fu-1.gitbook.io/oj/graph/1514.-path-with-maximum-probability.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.