ErdemT09
commented
3 years ago Thank you for your valuable collaboration Erdem.
Thank you for you collaboration too. I think we shouldn't try showing contradictions in algorithms by just brute counter-testing. That takes too much effort sometimes. Proving by contradictions in less direct manners is usually better in terms of logic too.
Problem: https://leetcode.com/problems/cheapest-flights-within-k-stops/
We can interpret this problem as a graph problem where we have to find the shortest path, set of "flights" from the source city to the destination. The graph here is a directed, weighted graph. So, it's only the most intuitive to use shortest path algorithms here. However, the number of edges we can traverse is limited by the number
K, We can't visit more thanK+1edges andK+2vertices.Approach-1: BFS:
I think this is the most simple one. In order not to visit more than limited number of nodes, we simply keep a check of how many layers of BFS we have done, as one can perhaps recall from #180. We do no more than K+1 layers of BFS, and eventually check for the minimum distance for the destination, or return -1 i we can't find it within K+1 layers of BFS.
Approach 2: DFS:
This is also a pretty simple modification. Only making K stops is also equivalent to applying the DFS algorithm to a depth of K+1. The minimum distance is then to be found within these searches. Since DFS contains making the same searches again, we can memoize these operations. Besides, we can prune our decision tree. If the current cost we get from DFS is more than the minimum global cost that we have found, we can avoid going any deeper.
Approach 3: Belmann-Ford Algorithm:
Belmann-Ford algorithm works by "relaxing" the edges. "Relaxation" simply means that if a distance to node would be updated iff the distance to a previous node + the edge weight yields a less distance. Normally, this relaxation process is done
|V|-1times, which is the maximum amount of nodes to be traversed in order to get to the destination. We can decrease this value to K+1 in order to only relax edges this many times, thus making at most K stops.In implementation, In order not to update the current distance array, we can create a temporary array. However, already having created 2 arrays and switching between these two for even and odd iterations. Doing this with bit-gates is pretty lean. It's not legible at first sight, but it's pretty great to use once learned.
Approach 4: Dijkstra's Algorithm:
The problem with the usage of Dijkstra's algorithm here is that, when we pick the shortest distance for a node and the path doesn't satisfy having K stops, there is no way of backtracking and picking the shortest path less than K stops. For this, we not only consider the distances of nodes but also the number of stops they have, thus storing multiple paths. When we are adding a node to the priority queue, we only add if it satisfies having a shorter distance or else having less number of stops. Either way, we update the current number of stops to the node, so that we prune the decision tree for adding the same node after adding this one.