題目原文 #
題目連結: 點我
You are given an undirected weighted graph of
nnodes (0-indexed), represented by an edge list whereedges[i] = [a, b]is an undirected edge connecting the nodes a and b with a probability of success of traversing that edgesuccProb[i].Given two nodes
startandend, find the path with the maximum probability of success to go fromstarttoendand return its success probability.If there is no path from
starttoend, 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^40 <= start, end < nstart != end0 <= a, b < na != b0 <= succProb.length == edges.length <= 2*10^40 <= 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 的解說影片，吐司覺得他說的很清楚，推薦給大家~~
以本題為例，簡單來說就是在遍歷的時候，我們可以先儲存從起點到該點的最大成功率，之後再從該點出發，前往相鄰的點並計算相鄰點的最大成功率。
與傳統 bfs 不一樣，我們會利用 heap 來儲存資料（本題使用的是 Max heap），用以決定下一步該訪問（visit）哪個點，heap 會自己幫我們比大小，可藉此提升效率；除此之外，為了提升效率，我們會利用判斷式來判斷是否該將資料存入 heap 中，不再訪問已訪問過的點。
然而，若每次訪問都必須從題目所給的 edges[] 與 succProb[] 中搜尋有與訪問點連接的邊的話，效率會有點低。所以，我使用了 hash table 來儲存每個點相鄰邊在 edges[] 中的 index ，以提升效率。
在C++中，我們會使用 priority queue 來實現 heap；用 unordered map 來實現 hash table。
流程圖 #
用流程圖表示大致如下:
Code: #
// 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 上跑的數字也不太好看😅
因此，我們可以試試看另一種方法 — 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 ~~
以本題為例，我們可以藉由遍歷 n-1 次 edges[] 來求出最大成功率。由於本題直接提供 edges[] 給我們，因此相較於 Dijkstra Algorithm，使用 Bellman Ford Algorithm 不用額外開一個 heap 來儲存資料，也不用紀錄該點是否訪問過，空間複雜度可大幅降低。
那時間複雜度呢？在邊數較多的測資中，由於 Bellman Ford Algorithm 不用整理 heap，因此執行效率會比 Dijkstra Algorithm 高出不少。
Code: #
// 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
Uva:
Uva929 - Number Maze
Uva10048 - Audiophobia
Uva821 - Page Hopping