Skip to main content

25. Modify Graph Edge Weights

hardAsked at Flipkart

Assign positive weights to '-1' edges so the shortest source-to-destination path equals a given target — Flipkart uses it to test Dijkstra fluency for warehouse routing under SLA constraints.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given an undirected weighted graph with some edge weights set to -1, replace every -1 with a positive integer in [1, 2*10^9] so that the shortest path from source to destination equals target. Return any valid edge list or [] if impossible.

Constraints

  • 1 <= nodes <= 100
  • 0 <= edges <= n*(n-1)/2
  • 1 <= target <= 10^9

Examples

Example 1

Input
n=5, edges=[[4,1,-1],[2,0,-1],[0,3,-1],[4,3,-1]], source=0, target=1, t=5
Output
[[4,1,1],[2,0,1],[0,3,3],[4,3,1]]

Example 2

Input
n=3, edges=[[0,1,-1],[0,2,5]], source=0, target=2, t=6
Output
[]

Approaches

1. Brute force enumerate

Try every assignment to unknown edges; check the shortest path.

Time
exponential
Space
O(E)
// blows up immediately past tiny inputs

Tradeoff:

2. Two-pass Dijkstra with adjustment

Pass 1 sets every -1 to 1 and runs Dijkstra; if the shortest path already exceeds target return []. Pass 2 iterates -1 edges in the order Dijkstra relaxes them and bumps each one up so the running shortest distance reaches target exactly.

Time
O(E * (E + V log V))
Space
O(E)
// 1) set all -1 to 1; run Dijkstra. If dist[dst] > target return []
// 2) re-run Dijkstra in a loop, each pass picking the next -1 edge
//    on the current shortest path and bumping it so the total = target.
// 3) after all -1 edges fixed, run Dijkstra again; if shortest != target
//    return [].
function modifiedGraphEdges(n, edges, src, dst, target) {
  // pseudocode — full Dijkstra omitted for space
  // shortest path with all -1 = 1 must be <= target
  // shortest path with all -1 = INF must be >= target
  // greedy bump each -1 in path order until we hit target exactly
  return edges; // after assigning weights
}

Tradeoff:

Flipkart-specific tips

Flipkart panels reward you for the two-bracket sanity check (min-weight Dijkstra <= target <= max-weight Dijkstra) before any greedy adjustment — it shows you reason about feasibility before coding.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Modify Graph Edge Weights and other Flipkart interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →