Shortest path from source to all vertices, but with some wildcards

Question

Here is problem in Sprinklr Interview Experience | Set 5 (On campus – FTE for Product Engineer).

You are given a graph of $n$ nodes with $m$ bidirectional edges. Each edge has some value associated with it. Vertex 1ドル$ is source vertex. You have $K$ wildcards. In the path from vertex 1ドル$ to vertex $i$ (2ドル \leq i \leq n$), you can use at most $K$ wildcards while traversing. When you use a wildcard on an edge, you can pass that edge in summing the cost of path (i.e., value of that edge will be 0ドル$ if you use a wildcard on an edge). Note: You can use at most $K$ wildcards from vertex 1ドル$ to vertex 2ドル$. Now you can again use at most $K$ wildcards from vertex 1ドル$ to vertex 3ドル$ and so on to vertex $n$. In other words, you can use at most $K$ wildcards in each path from source to destination. You have to find minimum distances from node 1ドル$ to all other nodes in graph.

Constraints: 1ドル \leq n, m \leq 500000, 1 \leq K \leq 15$

Expected Approach: DP with shortest path algorithms on graph.

What I am doing is that, we can choose $k$ edges from $m$ edges in $\binom{m}{k}$ ways. And for each case find shortest path, but that will be too much time complexity.

• phan801: What have you tried? Where did you get stuck?
• user99043: I tried this,choose edges k from m,which is m choose k. Remove them and find shortest path for each case.that is too much time complexity.
• user99043: geeksforgeeks.org/…

Answer 1

Take $K+1$ copies of your graph. For each edge $(x,y)$ and for each $i \in \{1,\ldots,K\}$, connect the $i$'th copy of $x$ to the $(i+1)$'th copy of $y$ with a zero weight edge. Also connect the $i$'th and $(i+1)$'th copies of each vertex with a zero weight edge. Now calculate the minimum distance between vertex 1 on the first copy to all vertices in the last copy.

I'll let you figure out why this works.

• Yuval Filmus: The graph that I construct is directed. You can only go forward.