### kickbust13's blog

By kickbust13, history, 10 months ago, ,

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.

• 0

 » 10 months ago, # |   +3 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)
•  » » 10 months ago, # ^ |   0 greg19 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??