A good way into this one is to ask: what do we need to remember so we never redo work blindly? For 1514. Path with Maximum Probability, the solution in this repository is mainly a heap / priority queue solution.
Guide
What?
The code is easier to read if we treat it as a controlled search through possible states. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: heap / priority queue, DFS + memoization, graph traversal, dynamic programming.
The notes already sitting in the source point us in the right direction:
- DFS
- TLE
- 10 / 16 test cases passed.
Guide
When?
Use this approach when the hard part is not syntax, but deciding what must stay true after every update. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are dfs, maxProbability, visited, maxProb.
Guide
Why?
The code is doing bookkeeping so your brain does not have to keep the entire search space open at once.
- The queue gives the solution a level-by-level or frontier-style traversal.
- The heap keeps the best candidate available without sorting the whole world every time.
- The two-dimensional vector is the memory of the solution: grid state, DP state, or adjacency shape.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Read the setup variables first.
- Follow the main loop or recursive helper next.
- Watch where invalid states get skipped.
- Check which value survives to the return statement.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(VE)
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01//DFS
02//TLE
03//10 / 16 test cases passed.
04class Solution {
05public:
06 vector<vector<pair<int, double>>> adj;
07
08 void dfs(int cur, int end, double prob, double& ans, vector<bool>& visited){
09 if(cur == end){
10 ans = max(ans, prob);
11 }else{
12 for(pair<int, double>& neiEdge : adj[cur]){
13 if(!visited[neiEdge.first] && prob * neiEdge.second > ans){
14 visited[neiEdge.first] = true;
15 dfs(neiEdge.first, end, prob * neiEdge.second, ans, visited);
16 visited[neiEdge.first] = false;
17 }
18 }
19 }
20 };
21
22 double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb, int start, int end) {
23 adj = vector<vector<pair<int, double>>>(n);
24
25 for(int i = 0; i < edges.size(); ++i){
26 adj[edges[i][0]].push_back({edges[i][1], succProb[i]});
27 adj[edges[i][1]].push_back({edges[i][0], succProb[i]});
28 }
29
30 // cout << "adj done" << endl;
31
32 double ans = 0.0;
33 vector<bool> visited(n, false);
34 visited[start] = true;
35
36 dfs(start, end, 1.0, ans, visited);
37
38 return ans;
39 }
40};
41
42//Bellman Ford
43//https://www.geeksforgeeks.org/bellman-ford-algorithm-dp-23/
44//http://courses.csail.mit.edu/6.006/spring11/lectures/lec15.pdf
45//TLE
46//10 / 16 test cases passed.
47//time: O(VE)
48class Solution {
49public:
50 double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb, int start, int end) {
51 //max probability from start node
52 vector<double> maxProb(n, 0.0);
53 maxProb[start] = 1.0;
54
55 //relax for |V|-1 times, because a simple path can have at most |V|-1 edges
56 for(int i = 1; i <= n-1; ++i){
57 //try to add one edge to paths
58 for(int j = 0; j < edges.size(); ++j){
59 //the graph is undirected!
60 maxProb[edges[j][1]] = max(maxProb[edges[j][1]], maxProb[edges[j][0]] * succProb[j]);
61 maxProb[edges[j][0]] = max(maxProb[edges[j][0]], maxProb[edges[j][1]] * succProb[j]);
62 }
63 }
64
65 return maxProb[end];
66 }
67};
68
69//Bellman Ford, BFS, SPFA(shortest path faster algorithm), not understand(does it repeat for |V|-1 times?)
70//https://leetcode.com/problems/path-with-maximum-probability/discuss/731626/Java-Detailed-Explanation-BFS
71//https://www.geeksforgeeks.org/shortest-path-faster-algorithm/
72//Runtime: 576 ms, faster than 12.50% of C++ online submissions for Path with Maximum Probability.
73//Memory Usage: 68.9 MB, less than 100.00% of C++ online submissions for Path with Maximum Probability.
74class Solution {
75public:
76 double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb, int start, int end) {
77 vector<vector<pair<int, double>>> adjList(n);
78
79 for(int i = 0; i < edges.size(); ++i){
80 adjList[edges[i][0]].push_back({edges[i][1], succProb[i]});
81 adjList[edges[i][1]].push_back({edges[i][0], succProb[i]});
82 }
83
84 //max probability from start node
85 vector<double> maxProb(n, 0.0);
86 maxProb[start] = 1.0;
87
88 queue<pair<int, double>> q;
89 q.push({start, 1.0});
90
91 while(!q.empty()){
92 pair<int, double> cur = q.front(); q.pop();
93 int curNode = cur.first;
94 double curProb = cur.second;
95
96 for(pair<int, double>& nei : adjList[curNode]){
97 int neiNode = nei.first;
98 double neiProb = nei.second;
99
100 if(curProb * neiProb > maxProb[neiNode]){
101 maxProb[neiNode] = max(maxProb[neiNode], curProb * neiProb);
102 q.push({neiNode, maxProb[neiNode]});
103 }
104 }
105 }
106
107 return maxProb[end];
108 }
109};
110
111//Dijkstra's algorithm
112//https://www.geeksforgeeks.org/dijkstras-algorithm-for-adjacency-list-representation-greedy-algo-8/
113//https://www.geeksforgeeks.org/dijkstras-shortest-path-algorithm-using-priority_queue-stl/
114//https://leetcode.com/problems/path-with-maximum-probability/discuss/731626/Java-Detailed-Explanation-BFS
115//Runtime: 460 ms, faster than 12.50% of C++ online submissions for Path with Maximum Probability.
116//Memory Usage: 66.2 MB, less than 100.00% of C++ online submissions for Path with Maximum Probability.
117//time: O((V+E)logV), we may push E elements into heap, and it takes O(logV) to pop, space: O(V+E)
118class Solution {
119public:
120 double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb, int start, int end) {
121 vector<vector<pair<int, double>>> adjList(n);
122
123 for(int i = 0; i < edges.size(); ++i){
124 adjList[edges[i][0]].push_back({edges[i][1], succProb[i]});
125 adjList[edges[i][1]].push_back({edges[i][0], succProb[i]});
126 }
127
128 //max probability from start node
129 vector<double> maxProb(n, 0.0);
130 maxProb[start] = 1.0;
131
132 auto comp = [](pair<int, double>& a, pair<int, double>& b){return a.second < b.second;};
133 priority_queue<pair<int, double>, vector<pair<int, double>>, decltype(comp)> pq(comp);
134
135 pq.push({start, maxProb[start]});
136
137 //while there are nodes that are not in SPT set
138 while(!pq.empty()){
139 /*
140 dijkstra's algorithm: greedy
141 it find the node with highest probability and
142 add it to the set containing all nodes already
143 included in SPT(shortest path tree)
144 */
145 pair<int, double> cur = pq.top(); pq.pop();
146 int curNode = cur.first;
147 double curProb = cur.second;
148
149 if(curNode == end){
150 /*
151 the node "end" has been added to SPT set,
152 that means we have found shortest path
153 from start to end
154 */
155 //early stopping?
156 //cannot do early stopping in bellman ford?
157 break;
158 }
159
160 //we still need to visit all neighbors of curNode, what's the meaning of using priority_queue?
161 for(pair<int, double>& nei : adjList[curNode]){
162 int neiNode = nei.first;
163 double neiProb = nei.second;
164
165 if(curProb * neiProb > maxProb[neiNode]){
166 maxProb[neiNode] = max(maxProb[neiNode], curProb * neiProb);
167 pq.push({neiNode, maxProb[neiNode]});
168 }
169 }
170 }
171
172 return maxProb[end];
173 }
174};
175
176//Floyd–Warshall
177//https://leetcode.com/problems/path-with-maximum-probability/discuss/731626/Java-Detailed-Explanation-BFS
178//https://www.geeksforgeeks.org/floyd-warshall-algorithm-dp-16/
179//TLE
180//9 / 16 test cases passed.
181//time: O(V^3)
182class Solution {
183public:
184 double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb, int start, int end) {
185 vector<vector<double>> maxProbs(n, vector<double>(n, 0.0));
186
187 for(int i = 0; i < edges.size(); ++i){
188 maxProbs[edges[i][0]][edges[i][1]] = succProb[i];
189 maxProbs[edges[i][1]][edges[i][0]] = succProb[i];
190 }
191
192 for(int k = 0; k < n; ++k){
193 for(int i = 0; i < n; ++i){
194 for(int j = 0; j < n; ++j){
195 //relax edge (i, j) with node k
196 maxProbs[i][j] = max(maxProbs[i][j], maxProbs[i][k] * maxProbs[k][j]);
197 }
198 }
199 }
200
201 return maxProbs[start][end];
202 }
203};Cost
Complexity
Time
O(VE)
Dominated by the main traversal, recursion, or data-structure operations in the code.
Space
O(n) in the usual case for auxiliary containers or recursion
Auxiliary state plus the answer structure where the problem requires one.