# 吐司寫LeetCode : 1514. Path with Maximum Probability
**topic: `Graph` `Shortest path`**
## 題目原文
題目連結: [點我](https://leetcode.com/problems/path-with-maximum-probability/?envType=daily-question&envId=2024-08-28)
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:**
>**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:**
>**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:**
>**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.
## 事先觀察
本題不難看出是一種 **shortest path** 問題。題目中，我們要尋找圖中從起點到終點成功機率（Success probability）最大的路徑。
圖中每條邊皆無方向性（代表兩邊都可走），且邊上皆有權重值，該權重值就是通過該邊的成功率。將通過路徑上的邊之成功率相乘後，便可得到從起點到終點成功率。然而成功率有很多結果，因此，本題想要我們選出最高的成功率。
## 修但幾勒
看到圖論題是不是就有 dfs 跟 bfs 的衝動呢?
由於本題圖上的點（Node）數量最多10000個，代表邊的總數可達49995000個。那麼大的數量，如果你要直接用傳統的**深度優先搜尋（Depth-first search, DFS）** 與 **廣度優先搜尋法（Breadth-first search, BFS）** 來試的話，一定會 TLE（Time limit Exceeded） 的。
那這時我們該怎麼辦呢？我們可以使用更高階的演算法來計算，以下提供了兩種方法。
## 方法1: Dijkstra Algorithm
### 描述
Dijkstra Algorithm 是一種改良型的bfs，常用於邊上有權重值的權重圖（Weighted graph）。這種方法要講解可以花很久，以後會再寫一篇文章來講解什麼是Dijkstra Algorithm（~~挖坑中XD~~）。
下面是外國大神ytr: **Abdul Bari** 的解說影片，吐司覺得他說的很清楚，推薦給大家~~
{%youtube XB4MIexjvY0 %}
以本題為例，簡單來說就是在遍歷的時候，我們可以先儲存從起點到該點的最大成功率，之後再從該點出發，前往相鄰的點並計算相鄰點的最大成功率。
與傳統 bfs 不一樣，我們會利用 heap 來儲存資料（本題使用的是 Max heap），用以決定下一步該訪問（visit）哪個點，heap 會自己幫我們比大小，可藉此提升效率；除此之外，為了提升效率，我們會利用判斷式來判斷是否該將資料存入 heap 中，不再訪問已訪問過的點。
(圖片來源: [geeksforgeeks](https://www.geeksforgeeks.org/difference-between-min-heap-and-max-heap/))
然而，若每次訪問都必須從題目所給的 `edges[]` 與 `succProb[]` 中搜尋有與訪問點連接的邊的話，效率會有點低。所以，我使用了 hash table 來儲存每個點相鄰邊在 `edges[]` 中的 index ，以提升效率。
在C++中，我們會使用 **priority queue** 來實現 heap；用 **unordered map** 來實現 hash table。
### 流程圖
用流程圖表示大致如下:
### Code:
```cpp= !
// Author: Toast1001
// Method: Dijkstra Algorithm
class Solution {
public:
double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb, int start_node, int end_node) {
vector<int32_t> vis(n, 0); // 紀錄該點是否被訪問過
vector<double> prob(n, 0); // 紀錄該點目前的最高成功率(預設值為0)
// 紀錄每個點的每個鄰邊在 edges[] 中的 index
unordered_map<int32_t, unordered_set<int32_t>> um;
for(int32_t i = 0;i < edges.size();i++){
int32_t x = edges[i][0];
int32_t y = edges[i][1];
um[x].insert(i);
um[y].insert(i);
}
// 建立 Max heap
priority_queue<pair<double, int32_t>> pq;
pq.push({1.0, start_node}); // 輸入第一個點
// 遍歷
while(!pq.empty()){
// 輸入位於 pq 頂層之點的資料
double np = pq.top().first; // 目前該點最高成功率
int32_t nn = pq.top().second; // 該點
pq.pop(); // 從 pq 中移除該點
// 判斷是否訪問過
if(vis[nn] == 1)continue;
// 更新資料
vis[nn] = 1;
prob[nn] = np;
// 尋找下一個訪問對象
// 藉由 um[nn] 尋找鄰邊
for(auto path: um[nn]){
// 邊的兩端點
int32_t x = edges[path][0];
int32_t y = edges[path][1];
// 由於 nn 可能位於兩端點中其中一個, 因此分為 nn 為 x 與 nn 為 y 兩種情形
if(x == nn){
// relax: 只有沒訪問過並且超過 prob[] 中的最高成功率才能放進 pq
if(np * succProb[path] > prob[y] && vis[y] == 0){
prob[y] = np * succProb[path];
pq.push({prob[y], y});
}
}else if(y == nn){
// relax: 只有沒訪問過並且超過 prob[] 中的最高成功率才能放進 pq
if(np * succProb[path] > prob[x] && vis[x] == 0){
prob[x] = np * succProb[path];
pq.push({prob[x], x});
}
}
}
}
// 回傳終點最高成功率
return prob[end_node];
}
};
```
### 結果
然而，因為每次訪問完都有可能要重新整理 heap，若在邊數較多的測資，dijkstra algorithm 會有效率降低的問題，在 Leetcode 上跑的數字也不太好看:sweat_smile:
因此，我們可以試試看另一種方法 — **Bellman Ford Algorithm**
## 方法2: Bellman Ford Algorithm
### 描述
**Bellman Ford Algorithm** 也是一種改良型的bfs，常用於邊上有權重值的權重圖（Weighted graph），相較於 Dijkstra Algorithm，Bellman Ford Algorithm 可處理一些 Dijkstra Algorithm 無法處理的問題，像是邊權重值有負值的狀況。
同樣的，也推薦看 **Abdul Bari** 的解說影片，吐司之後也會再做一篇文章來講解 Bellman Ford Algorithm ~~
{%youtube FtN3BYH2Zes %}
以本題為例，我們可以藉由遍歷 **n-1** 次 `edges[]` 來求出最大成功率。由於本題直接提供 `edges[]` 給我們，因此相較於 Dijkstra Algorithm，使用 Bellman Ford Algorithm 不用額外開一個 heap 來儲存資料，也不用紀錄該點是否訪問過，空間複雜度可大幅降低。
那時間複雜度呢？在邊數較多的測資中，由於 Bellman Ford Algorithm 不用整理 heap，因此執行效率會比 Dijkstra Algorithm 高出不少。
### 流程圖
用流程圖表示大致如下:
```flow
st=>start: start
i=>input: 輸入資料
op1=>operation: 初始化prob[]
並將prob[start_node]設為1
sub=>subroutine: 遍歷所有邊並更新各邊兩端點
cond=>condition: 本次遍歷是否有更新點?
o=>output: 輸出終點最大成功率
op3=>ope
e=>end: end
st->i->op1->sub->cond
cond(yes)->sub
cond(no)->o->e
```
### Code:
```cpp= !
// Author: Toast1001
// Method: Bellman Fold Algorithm
// TC: O(n*E)
// SC: O(n)
class Solution {
public:
double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb, int start_node, int end_node) {
// 初始化
vector<double> prob(n, 0.0); // 目前該點的最大成功率
prob[start_node] = 1.0; // 設起點為1
// 遍歷 n-1 遍
for(int32_t i = 0;i < n - 1;i++){
bool change = false; // 偵測本次遍歷是否有更新任何點
// 遍歷所有邊
for(int32_t j = 0;j < edges.size();j++){
// relax: 只更新超過 prob[] 中最大成功率的點
if(prob[edges[j][0]] * succProb[j] > prob[edges[j][1]]){
prob[edges[j][1]] = prob[edges[j][0]] * succProb[j];
change = true; // 有更新
}
if(prob[edges[j][1]] * succProb[j] > prob[edges[j][0]]){
prob[edges[j][0]] = prob[edges[j][1]] * succProb[j];
change = true; // 有更新
}
}
// 判斷本次遍歷是否有更新
// 若沒有: 退出迴圈
if(!change)break;
}
// 回傳終點最大成功率
return prob[end_node];
}
};
```
### 結果
本題使用 Bellman Ford Algorithm 較快，用 Leetcode 跑出來的效率也頗高的。
因此．若在邊數較多且 Dijkstra Algorithm 效率較低的時候，可以試試看 Bellman Ford Algorithm 哦~
## 小結
本題所出現的權重圖問題在資訊領域中十分常出現，所以學會處理這種問題是十分重要的～
此外，這是吐司編第一次寫 LeetCode 解析，若有文筆不通順的地方，或是有更好的解法，都可以在下面提出哦～
吐司寫 LeetCode，我們下次見，bye~ bye~
## 類題
**LeetCode:**
[1976. Number of Ways to Arrive at Destination](https://leetcode.com/problems/number-of-ways-to-arrive-at-destination/)
**Uva:**
[Uva929 - Number Maze](https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=870)
[Uva10048 - Audiophobia](https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=989)
[Uva821 - Page Hopping](https://onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=762#google_vignette)
Sign in with Wallet
Connect another wallet