Path with Maximum Probability - Leetcode 1514 - Python

[@adams0078]

Please, don't stop making these videos, they are really helpful! Thanks man!

[@shirastromer]

I suggest to use dict instead of lists when construction the graph (beats 95%) def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start_node: int, end_node: int) -> float: res = 0 graph = collections.defaultdict(dict) # constructing a graph for (source, dest), prob in zip(edges, succProb): graph[source][dest] = prob graph[dest][source] = prob heap = [] heapq.heapify(heap) heapq.heappush(heap, (1, start_node)) visited = set() while heap: node_prob, node = heapq.heappop(heap) if node == end_node: return abs(node_prob) visited.add(node) for child in graph[node]: if child not in visited: heapq.heappush(heap, (-abs(node_prob) * graph[node][child] ,child)) return 0

[@Munchen888]

Thanks for good explanation ) Really, your dry run code helps to understand working of algorithm.

[@xiaoshen194]

What if while being greedy, we choose let's say 0.5 over 0.2 but then later on 0.5 path would have multiple 0.1s and 0.2 path would have all, say 0.99s. Would this approach still work?

[@NeetCodeIO]

Yes

[@cosepeter2197]

Are you saying that .5 path is connected to a path of .1 probability? If so, .5*.1 = .05 hence .05 would be pushed to the priority queue and now max value in priority queue is .2 and that would be popped and neighboring nodes would be searched. Let's say .2 has neighbor with .99, now .2*.99 = 0.198. Hence this value would be the max in the priority queue and this path would be preferred. Hope this makes sense.

[@xiaoshen194]

@@cosepeter2197 thnx 🙏

[@laural4976]

Yes, because the heap you are using always gives you the path of maximum probability (of all paths being currently traversed). If you choose the 0.5 path that ends up having lower probability down the path it wouldn't be at the top of the heap after you append it.

[@sickboydroid]

@laural4976 is right, its not like you are abandoning the other possibilities but just postponing them till the 0.5 path leads to something which is less than 0.2

[@ksaigon]

Hey, thank you for the video. I had the same idea to basically do reverse Dijkstra's - though all resources I've found online states that you cannot modify Dijkstra's algorithm to find the longest path (unless it's a DAG - which I think ours is clearly not). Could you give an insight into why this works? I'm not sure I'm quite understanding the explanation in the video.

[@cosepeter2197]

Awesome video .

[@NeetCodeIO]

Here is today's daily LC if you're looking for it: kzbin.info/www/bejne/oZbYiH1qbN16bsk

[@birdbeakbeardneck3617]

i never wrote graph algorithms just watched them onn youtube but am wondering if you took the log of every probability on each edge thatll spit out a negative number then you run dijkastra which will give the route with meanimium distance. the distance will be equal to ln(p1)+ln(p2)+...+ln(pn) = ln(p1*...*pn), and since minimizing the ln(prod pi) minimizes P=prod pi, dijkastra should sufice

[@KPCoder]

Thanks

[@krateskim4169]

thank you

[@aniketmahangare8333]

Why will there be max V^2 elements in the heap??

[@xiaoshen194]

Yes my question also same no difference

[@Snoresville]

there are cases where all of the nodes are connected to each other, so at the first iteration we might need to add V-1 nodes, and the second we might add V-2 and so on, eventually reaching to that worst case V^2 space complexity

[@aniketmahangare8333]

@@Snoresville got it, thanks

[@kareni7572]

🤩

[@bjhhar1233]

Just quick fyi, it's pronounced DIKE-struh's algorithm. Good video though :]

[@nehaagrawal25]

Why can't we use simple dfs and dp here? Below olution gives me wrong ans not sure why? class Solution { public: double f(int currIndx, int end, vector& edg, int n, vector& vis, vector& dp) { if(currIndx == end) { return 1; } if(dp[currIndx] != -1) return dp[currIndx]; double ans = 0; for(int i = 0; i < n; i++) { if(!vis[i] && currIndx != i && edg[currIndx][i] != -1) { vis[i] = 1; ans = max(ans, edg[currIndx][i] * f(i, end, edg, n, vis, dp)); vis[i] = 0; } } return dp[currIndx] = ans; } double maxProbability(int n, vector& edges, vector& succProb, int start, int end) { vector vis(n, 0); vector edg(n, vector(n, -1)); int noOfEdges = edges.size(); for(int i = 0; i < noOfEdges; i++) { int u = edges[i][0]; int v = edges[i][1]; edg[u][v] = succProb[i]; edg[v][u] = succProb[i]; } vis[start] = 1; vector dp(n, -1); return f(start, end, edg, n, vis, dp); } };

[@SohamKayal-ju6sn]

When you use dp the dp[i] is either -1 or any other value If dp[i] is 0.25 and max probability to reach that node can be 0.3, the 0.3 possibility will be ignored since at that time dp[i] is not -1

[@sonicjetson6253]

you should try to be less verbose. just too may words blah blah.