kickbust13's blog

k skip shortest path.
By kickbust13, history, 17 months ago, In English

can anyone help in solving the following question.

consider a weighted undirected graph. There is a source S and destination D and a value K. Find the length of the shortest path such that you can make at most K edges 0.

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (4)
»
17 months ago, # |
  Vote: I like it +3 Vote: I do not like it

We can create a graph with $$$k$$$ layers — lets call it $$$G[n][k]$$$. For each edge $$$(v,u,w)$$$ we add two types of edges to our graph:

  • $$$G[v][i]$$$ — $$$G[u][i]$$$ with weight $$$w$$$ (standard edge, needs to be in each layer)

  • $$$G[v][i]$$$ — $$$G[u][i+1]$$$ with weight $$$0$$$ ("skipping" edge, also in each layer)

Now if we calculate minimum distances to each vertex in the whole graph, distance to $$$G[v][l]$$$ will mean minimum distance to vertex $$$v$$$ if we made exactly $$$l$$$ edges to be equal 0.

If the weights are positive we can use Dijkstra's algorithm to calculate minimum distances giving us $$$O(nk*log(nk))$$$ complexity.

If weights can be negative we use Bellman–Ford algorithm giving us $$$O(n^2k^2)$$$ comlpexity.

Note that we need to take minimum distance to $$$d$$$ in all layers in order to find the answer (we "skip" at most $$$k$$$ edges)

→ Reply
  • »
    »
    17 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Greg. thanks for the solution. Can you please elaborate the process of adding an edge in the graph. And is it possible to have a dp solution??

    → Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone give link to problem of this type on codeforces

→ Reply