Path with Maximum Probability - Leetcode 1514 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem path with maximum probability we are given an undirected weighted graph of nodes which is of course represented with a list of edges they are undirected so we can go in either direction but the weight itself actually represents a probability in this case we're also given a starting node and an ending node in this case 0 is our starting node two is the ending node we want to find the path with the maximum probability of success going from zero and ending at two if no path exists then we return 0 if the path does exist we return the probability of success along that path the first thing you might want to try is a Brute Force solution why not just calculate everything single possible path from zero to the ending node among all of those paths we pick the one that has the max probability and then return the probability that's definitely a valid way to do this but it's not very efficient doing a rough time complexity analysis it's sort of going to be a backtracking approach doing it this way where every time we visit a node we're going to have a bunch of choices the total number of choices could be the total number of edges that we have in the graph let's say that's e we're going to keep going along a path let's assume that these are like particular paths that we're going to try to enumerate we're going to try to get every possible path in the graph so the length of a path is going to be V where V is the number of nodes in the graph now this is definitely an upper bound but it shows you that this is going to be exponential time complexity that's the important part roughly I think this is going to be e to the power of V though in most cases it's going to be much smaller than this but still this is going to be an exponential time complexity function but there is a better way and the hint to figuring that out is that the weights in this case are always going to be a value between 0 and 1. so as we travel along a path let's assume we go here and then we go here our total probability is never going to increase we started here with 0.5 are we ever going to find a number along this path that we can multiply this by that's going to increase this value no we're never going to because the value is between 0 to 1. the value is either going to stay the same or get smaller and that just has to do with the way probabilities are calculated for example if we have a probability of successfully traveling across this with 0.5 like a 50 probability and then we want to go here right after we we do that how do we find the total probability well this is just high school math we take these two and multiply them together and the value gets smaller instead of getting bigger so 50 times 50 is actually 25 that's the chance of success going along this path but notice how that's bigger than the other possibility which is to go in this Direction that's only a 20 chance which is 0.2 so what I'm getting at is that we can be greedy in this case when we start at zero we know which side would we rather go would we rather go this direction or this direction well we don't know for sure which path is going to lead us to a higher probability but we know we should probably try this path first because it has a higher probability 50 we know this 20 is never going to get higher but this 50 might get lower maybe it'll end at 25 percent like we saw but that's still going to be higher than this 20 so we can be greedy what's a good greedy algorithm we could run on this well it's a pretty famous shortest path algorithm it's called dixtra's algorithm we are going to use it instead of finding the shortest path we're going to find the maximum probability it's going to be very similar except instead of trying to minimize the distance we're going to try to maximize the probability I'll briefly go over how it's going to run in our case basically we're going to have a heap in our case it's actually going to need to be a Max Heap because we're trying to maximize the probability we're going to start at the source node 0. we're going to add its two neighbors here we know that one neighbor is the node one the probability of going along that path is going to be 20 we have a second neighbor 2 or actually that was two two is the neighbor here sorry if this is a little bit unreadable and we have another neighbor one over here and to travel to that node we have a 50 probability Dexter's algorithm is greedy so in this Max Heap we're gonna pop the value with the highest probability so the key that we're going to use in this case is going to be the probability one quick note in Python there aren't Max heaps by default there's only Min heaps so we can get around that by taking these weights and multiplying them to be negatives notice which one of these is smaller negative 0.5 is smaller than negative 0.2 so we would end up popping this first that's just something we have to do in Python unfortunately so in this case we're going to end up popping this guy we're trying to be greedy so then we're going to end up visiting Node 1 over here and now we're going to add its neighbors to the Heap as well in this case we're adding this node to twice to the Heap the second time we add it we want to know the probability of getting to this node traveling along this path which is going to be 0.5 the probability to reach 1 in the first place multiplied by the probability ability to reach 2 which is going to be 0.25 so we have this node here on the max Heap twice but the key is going to be the probability that's what we're going to use to figure out which one of them is the maximum and now we're going to pop one more time the maximum probability which is this so we pop it and we see we have reached the destination remember the ending goal in this case was the node two we've reached it and the first time we reach it we know that this is the maximum probability that we could possibly get which is 0.25 so that's what we would return in this case and this is more efficient in the worst case we're gonna have to visit every single node once like we're gonna have to pop from the max Heap once we might end up adding the same node multiple times but that's okay the max number of times we might add a node to the Heap is going to be V squared or at least that's the max size our Heap could be so V is the number of vertices V squared is much bigger than that but every time we pop from the Heap it's going to be log of the size of the heat now if you remember from math which you probably don't you probably don't necessarily need to but log V squared is actually we can take this value and put it over here it's actually 2 times log V and we know we don't care about constants so this is not a big deal popping from this is going to be log V we're going to have to do it in the worst case for every Edge in the graph which e is how we represent that but e is bounded by V squared so you can write this however you want a lot of people write dixtra's time complexity to be e Times log V I think V squared is also correct but this is just an upper bound this is probably the most precise way that people write it but clearly this is better than an exponential time complexity okay now let's code it up so the first thing I'm going to quickly skip is just building our adjacency list this isn't something super fancy you usually have to do it for graph problems where we're just given a list of edges so in Python I'm creating a map where the default value is going to be an empty list then we're going to go through every Edge in the input we're going to get the source node and the destination node though it doesn't really matter because these nodes are undirected but I'm going to say for this Source node I want to append to its list of neighbors the destination node we also want to be able to keep track of the probability for every single edge so we add two values we add the destination node and the probability of reaching that node and vice versa we take the destination node and append to it the source node and the probability of reaching that Source node this default dict and setting it to a list here just means that if we use a key like this source and we try to append to it before we even inserted a list in the first place this won't throw an error it'll just automatically initialize this to an empty list so that we can append to it so this just removes the need for us to add an extra if statement here now for dixtra's algorithm we are going to initialize a priority queue in Python that's just an array and we're going to have a pair of values actually the key I'm going to set to be negative one the reason it's negative is because in Python this is going to be a Min Heap but we can simulate it to be a Max Heat by using negative key values and the reason it's one is because we initially just want to assume our probability is one because when we calculate the probability we're just going to start multiplying the real probabilities one is a neutral value it won't mess up the calculation if we set it to zero then that would be bad because anytime we multiply a probability by zero it's still going to be zero that's not going to give us the right answer but 1 is a neutral value that we can use it won't mess up our calculation the starting node of course is going to be a parameter start that's passed in up above and that's what's going to be the only node in our priority queue initially we don't want to end up visiting the same node twice ISO we're going to have a hash set to not do that technically it's possible we could pop the same node from the Heap queue multiple times but then we won't end up adding any of its neighbors while the priority queue is non-empty we're gonna pop from it we're gonna pop two values of probability and the current node and to pop from them in Heap in Python we can just say Heap Q dot Heap pop from the priority queue this is our pair of values as soon as we pop we want to mark that node as being visited so that we don't visit it multiple times we also want to check have we already reached the destination if we have then we can go ahead and return the probability it takes to reach that node which is what we added to the Min Heap and what we popped from them and Heap up above but remember it was a negative value that's what we're going to be adding to the heaps to make it positive we're going to just multiply it by negative one before we return it though if we don't find the ending node then we want to go through all the neighbors of the current node and add them to the Heap so we're going to say neighbor and Edge probability in the adjacency list of the current node remember we added pairs of values so we're going to be popping those pairs the first value was the node the second value was the probability that's what we have here and this probability was just the edge probability for just a single edge what we're going to say now is as long as this neighbor has not already been visited then we can push it to the Heap queue even if it's already been pushed to the Heap because maybe this is a shorter path or AKA a more maximum probability to reach that node we're going to say to the Heap Q push this pair of values first of all we want to add the probability we know that's the first value that's going to go in our Heap because that's going to be used as the key value for the Heap how do we calculate the probability of reaching this neighbor going through this current node well the probability to reach that current node was this probability so prob multiplied by the probability of traversing The Edge which luckily we have right here times Edge prob and that's going to be the probability now the second value we also want to make sure to add the node itself because we want to be able to pop that as well so we're going to say neighbor so this is the pair of values we're pushing to the Heap this is what's going to be used as the key that is actually the entire code if we do find a solution we're going to return it right here and this is actually always going to be negative because we started with a negative 1 here and Edge prob is always going to be positive because we never multiplied those edges by negative one when we actually added them and those were all positive values that we were passed in every time we append or push to the Heap the probability is always going to be negative if we never find a solution we have to make sure to return 0 outside of the loop now let's run the code to make sure that it works and as you can see yes it does and it's pretty efficient if this was helpful please like And subscribe if you're preparing for coding interviews check out neatco.io it has a ton of free resources to help you prepare thanks for watching and hopefully I'll see you pretty soon