I appeared for Flipkart coding test day before yesterday and got stuck on this problem:
You are given an undirected weighted graph with n vertices and m edges. In one move you can make any edge weight zero. You can perform atmost K moves. You have to tell what is the shortest path from a starting node A to an ending node B after performing atmost K moves.
1<=n<=1000
0<=K<n
1<=m<=10000
1<=w<=10^9 (weight of edge)
Can anybody please tell me how to approach this problem?
I found this problem on quora also but couldn't understand the approach clearly.
[UPD]: This problem has been solved thanks to ExplodingFreeze and _dobby_
Code
Auto comment: topic has been updated by Rock2000 (previous revision, new revision, compare).
I think we can consider all the path from A to B. Now for each path $$$P_i$$$ let's say $$$e_i$$$ be the no of edges so pick least $$$max(0,e_i-k)$$$ edges w.r.t weight and update the final result.
Can you tell me what is the time complexity of your solution?
Its trivial to make the number of paths exponential. Consider the following construction:
Now there are 2 ways from 1 -> 4, 4 from 1 -> 7, 8 from 1 -> 10 and so on. So we can easily make a graph with $$$2^{\frac{n - 1}{3}}$$$ paths using $$$n$$$ nodes and the naive solution of using all paths will TLE.
Please share ,where you got infos of these types of test . I am searching for an offcampus internship. How to get a chance .
It was oncampus.
It is the same problem as here K was small. I dont know what was value of k in your case but if k is small we can use a modified dijskarts to solve this problem. Link to original problem ..Problem.
Auto comment: topic has been updated by Rock2000 (previous revision, new revision, compare).
So we effectively want to find the shortest path from $$$A$$$ to $$$B$$$ such that we skip the weight of at max $$$k$$$ edges. So if there removal of edges wasn't there this would be a pretty simple Dijkstra problem, right? So is there some way to interpret the problem differently such that we can still use Dijkstra?
Lets examine the transitions between nodes. Say we are at $$$x$$$ and $$$v$$$ is some node adjacent to $$$x$$$. Lets also suppose we have skipped $$$y$$$ edges till now. When we move to $$$v$$$, we have to decide whether to skip this edge or not:
We can choose to add the weight of the edge to the answer we will now be at node $$$v$$$ have skipped $$$y$$$ edges.
We can choose to skip this edge we will be at node $$$v$$$ having skipped $$$y + 1$$$ edges.
In both cases there can be many ways (or possibly none) to reach each node for a specific count of edges skipped, and clearly the current state depends on nothing except these the current node and the number of edges skipped. So we just want to find the shortest path from node $$$A$$$ with $$$0$$$ edges skipped to node $$$x$$$ skipping $$$y$$$ edges. Or in other words, we want to find the shortest path to each pair {$$$x, y$$$}. And from some {$$$x, y$$$} we can move to {$$$v, y$$$} (where $$$v$$$ is adjacent to $$$x$$$) at a cost of the edge between them, or to {$$$v, y + 1$$$} at zero cost. Now we can notice this is effectively applying Dijkstra to the state { node, edges used } with the two moves being "edges" to the adjacent states. And we finally want the shortest path to $$$B$$$ skipping at max $$$k$$$ edges, so the answer will be the minimum of all {$$$B, y$$$} for all $$$0 \leq y \leq k$$$.
We have $$$n \times k$$$ states and $$$2 \times m \times k$$$ edges, so the total complexity is $$$O(m \times k \times log(n \times k))$$$ which should pass if $$$k$$$ isn't too large. $$$k \leq 1000$$$ should work as long as the time limit isn't too strict.
Thank you very much. I was thinking in the same way but wasn't able to figure out that node will be {node,edges used} in dijkstra.
If A and B are not in the same component, then it is not possible.
Now, if $$$K \geq n$$$, then the answer is always $$$0$$$, as there definitely is a path with less than or equal to $$$n − 1$$$ edges, between A and B, so you can make all these $$$0$$$ (and some of the remaining extra edges, to complete the $$$K$$$ count).
Now, $$$k < n$$$, so $$$k < 1000$$$.
Let dp[i][j] be the minimum distance from A to node $$$i$$$ with $$$j$$$ moves used, where $$$1 \leq i \leq n$$$, and $$$0 \leq j \leq k$$$. This can be calculated in a similar fashion to Dijkstra's.
Misread parent comment.
Yes, the time complexity is $$$O(m \cdot K + n \cdot K \cdot log(n \cdot k))$$$, which is slower than $$$O((n + m) * K)$$$
I misread your comment and thought you were directly performing a dp of some sorts, not Dijkstra >.> .
Hi brother..i have a doubt why can't we just find the shortest path in the original graph between node a and node b and that would be our answer because we can apply k operation in this shortest path thus reducing it even further.
What if there is a path with one edge with a huge weight but others with less weight?
Thanks bro.
Could you please elaborate this solution. I am not able to understand how the time complexity is brought down to
O((n+m)*K)using this.The complexity is not reduced, my solution runs in $$$O(m \cdot K + n \cdot K \cdot log(n \cdot k))$$$, which is slower than $$$O((n + m) * K)$$$.
Auto comment: topic has been updated by Rock2000 (previous revision, new revision, compare).