The Modify Graph Edge Weights problem gives you a weighted directed graph where some edge weights are set to -1 (meaning they can be assigned any positive integer). You also have a source, destination, and target distance. Your task is to assign values to all -1 edges such that the shortest path from source to destination equals exactly the target. This hard Modify Graph Edge Weights coding problem requires careful integration of Dijkstra's algorithm with constraint assignment.
Google and Bloomberg ask this hard problem to test Dijkstra mastery combined with constraint-satisfaction reasoning. It requires two Dijkstra runs — one to check feasibility without the -1 edges and one to iteratively assign values — making it a sophisticated graph design challenge. The shortest path, graph, and heap interview pattern is the core, and the problem tests whether candidates can think algorithmically about edge weight assignment.
Two-pass Dijkstra. First, set all -1 edges to 1 and run Dijkstra. If shortest path < target, the target is unreachable (even with minimum weights). Second, set all -1 edges to a large value and run Dijkstra. For each -1 edge (u, v) in order, assign its weight such that dist[u] + weight + distFromV[dest] = target. Adjust and re-run until the target is achieved exactly.
Graph: nodes 1-4. Edge (1,2)=-1, edge (2,4,3), edge (1,3,1), edge (3,4,5). Source=1, dest=4, target=6.
Graph problems requiring "assign values satisfying a constraint" need a two-phase approach: check feasibility first, then construct the solution. For Dijkstra-based constraints, always verify the boundary cases (min possible and max possible path lengths) before attempting assignment. Practice standard Dijkstra fluently — this problem adds complexity on top, and any implementation bugs in the base algorithm will derail the entire solution.
