1514. Path with Maximum Probability | BFS | DFS | Leetcode POTD Explained

[@codeby_naruto]

Code :- class Solution { public: double maxProbability(int n, vector& edges, vector& succProb, int start_node, int end_node) { vector adjList(n); for (int i = 0; i < edges.size(); i++) { int u = edges[i][0]; int v = edges[i][1]; adjList[u].push_back({ v, succProb[i] }); adjList[v].push_back({ u, succProb[i] }); } vector maxProb(n, 0); maxProb[start_node] = 1.0; priority_queue pq; pq.push({ 1.0, start_node }); while (!pq.empty()) { auto curr = pq.top(); pq.pop(); double currProb = curr.first; int currNode = curr.second; if(currNode==end_node) return maxProb[end_node]; for (auto node : adjList[currNode]) { int nextNode = node.first; double nextProb = node.second; if (currProb * nextProb > maxProb[nextNode]) { maxProb[nextNode] = currProb * nextProb; pq.push({ currProb * nextProb, nextNode }); } } } return maxProb[end_node]; } };