Advanced Graphs Flashcards
Cheapest Flights within K stops
We can use the Bellman-Ford Algorithm here. Essentially we have a list of prices to get to each airport (we can just use an array and index via airport num). The prices start at infinity. Then we iterate over all edges k + 1 times (as 1 stops means we can visit 2 airports including the destination). We set up a temporary prices array which is a copy. So for each edge, if the price of its source airport is infinity, we know that edge is a level past what we should be exploring at this current iteration. So why iterate through all edges? Can’t we just use traditional BFS to exclude the edges that are too far out. Well we could but it would complicate the code a bit, so the check if the source node is infinity works well enough here.
So after that you check if the price of the source airport + the price of travel to this new destination is greater than the price of the destination in our temp prices array. If it is we update the temp prices array. Once we finish iterating through all edges, we set the prices array equal to the temp prices array.
The reason we need the temp prices array is to prevent putting multiple edges into a single level of traversal
For example say we had a graph with nodes A -> B (100), A -> C (500), and B -> C (100). If we updated prices with the edge A -> B. The cost of B is now 100, not infinity. So now when we go over edge B -> C. We find that its a cheaper way to get to C, so we update it. But that means we’ve gone over two airports (including the destination) in a single iteration of our loop.
Network Delay
Construct a graph as usual and run djikstras, which is implemented as a BFS, just with a minheap instead of a regular queue. All you have to do is heap.heappop() and heapq.heappush(). Maintain your visited set as usual. The minHeap should contain a tuple with the first element being distance from source and the second being the nodes value. When adding to the minheap, remember to add distance from the current node to its neighbor PLUS the distance to the current_node from source.
Then upon visiting each node, simply check if its distance from source is greater than the highest value so far (or float(“-inf”) or something) and update it. That is the value you return
Min Cost to connect all points
The goal here is to create a Minimum Spanning Tree. We can do this with Prims algorithm.
We’ll create a list of all possible edges first. Remember to cast points to a tuple. The value in this map should be a tuple with the first element being distance and the second being the destination point
So then you cretae your minheap, initialized with (0, tuple(points[0]) as well as a visited set.
Then you do your traditional while minHeap stuff, add to visited, and update the cost with the cost of the current node.
Then you loop through all the edges this node has and heappush them.
So the pattern is visitin a node with the smallest distance, adding the cost of that node to the total, and adding all its edges to the minheap. Repeat.
Swim in Rising Water
Really we are just trying to find the shortest path to the bottom right square. “Shortest” here just means whichever path has the smallest max height. So keep track of the max height. When you add to the minHeap, put in (grid[r][c], r, c) and add (r, c) to visited.
When adding to the queue, go out in all directions from the current square. And then at the highest while loop, pop the smallest grid in the heap, update max_height appropriately and if the coordinates are that of the bottom right suqare, return.
