### kickbust13's blog

By kickbust13, history, 5 years 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

| Write comment?
 » 5 years 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)
•  » » 3 years ago, # ^ |   0 Why we need to take minimum in all layers , should n't the minimum should be when you have skipped k edges . i.e G[dest][k] ??
•  » » » 3 years ago, # ^ |   0 Because you can skip at most $k$ edges. It's unnecessary for positive weights, but for negative weights can result in wrong answers.
•  » » 10 months ago, # ^ |   0 What does 'i' represent here? Can you provide a picture of any example?
 » 4 years ago, # |   0 can someone give link to problem of this type on codeforces
•  » » 3 years ago, # ^ |   0 Here is one from codeforces.
 » 3 years ago, # |   0 CODE with explanation void findMinDistance(vector> adj[], int N, int k) { // {dist, {node, leftout}} priority_queue>> pq; pq.push({0, {1, 0}}); int dist[N + 1][k + 1]; for (int i = 0; i <= N; i++) { for (int j = 0; j <= K; j++) { if (i == 0) dp[i][j] = 0; else dp[i][j] = INT_MAX; } } while (!pq.empty()) { // it -> {dist, {node, leftout}} auto it = pq.top(); pq.pop(); int node = it.second.first; int x = it.second.second; int dis = dist[node][x]; // it.first // iterate over all adjacent nodes for (auto iter : adj[node]) { int y = iter.first; int d = iter.secoond; // at first lets do without leaving out any edges if (dis + d < dist[y][x]) { dist[y][x] = dis + d; // pq is max heap, but i need minimal distance at top // so to make sure the max heap is used as // min heap, i converted it by having negatives, so // that max heap works in opposite pq.push({-1 * (dis + d), {y, x}}); // why did i take -1 ? } // if the max turn off edges have been done, // no need to further turn off edges if (x == k) continue; if (dis < dist[y][x + 1]) { dist[y][x + 1] = dis; // pq is max heap, but i need minimal distance at top // so to make sure the max heap is used as // min heap, i converted it by having negatives, so // that max heap works in opposite pq.push({-1 * (dis), {y, x + 1}}); // why did i take -1 ? } } } int mini = INT_MAX; // in reaching N, you can take any dist // by turning of 0, 1, 2, 3, 4, 5,... edges for (int i = 0; i <= k; i++) mini = min(mini, dist[N][i]); return mini;}