Modify Graph Edge Weights

Hard

#2439Time: O(E + V log V) for a single run of Dijkstra's algorithm with a priority queue.Space: O(V + E), where V is the number of nodes and E is the number of edges, for storing the graph and Dijkstra's data structures.

Algorithms

Shortest Path

Data structures

Heap (Priority Queue)Graph

Prompt

You are given an undirected weighted connected graph containing n nodes labeled from 0 to n - 1, and an integer array edges where edges[i] = [a_i, b_i, w_i] indicates that there is an edge between nodes a_i and b_i with weight w_i.

Some edges have a weight of -1 (w_i = -1), while others have a positive weight (w_i > 0).

Your task is to modify all edges with a weight of -1 by assigning them positive integer values in the range [1, 2 * 10⁹] so that the shortest distance between the nodes source and destination becomes equal to an integer target. If there are multiple modifications that make the shortest distance between source and destination equal to target, any of them will be considered correct.

Return an array containing all edges (even unmodified ones) in any order if it is possible to make the shortest distance from source to destination equal to target, or an empty array if it's impossible.

Note: You are not allowed to modify the weights of edges with initial positive weights.

Example 1:

Input: n = 5, edges = [[4,1,-1],[2,0,-1],[0,3,-1],[4,3,-1]], source = 0, destination = 1, target = 5
Output: [[4,1,1],[2,0,1],[0,3,3],[4,3,1]]
Explanation: The graph above shows a possible modification to the edges, making the distance from 0 to 1 equal to 5.

Example 2:

Input: n = 3, edges = [[0,1,-1],[0,2,5]], source = 0, destination = 2, target = 6
Output: []
Explanation: The graph above contains the initial edges. It is not possible to make the distance from 0 to 2 equal to 6 by modifying the edge with weight -1. So, an empty array is returned.

Example 3:

Input: n = 4, edges = [[1,0,4],[1,2,3],[2,3,5],[0,3,-1]], source = 0, destination = 2, target = 6
Output: [[1,0,4],[1,2,3],[2,3,5],[0,3,1]]
Explanation: The graph above shows a modified graph having the shortest distance from 0 to 2 as 6.

Constraints:

1 <= n <= 100
1 <= edges.length <= n * (n - 1) / 2
edges[i].length == 3
0 <= a_i, b_i< n
w_i = -1 or 1 <= w_i<= 10⁷
a_i!= b_i
0 <= source, destination < n
source != destination
1 <= target <= 10⁹
The graph is connected, and there are no self-loops or repeated edges

Approaches

2 approaches with complexity analysis and trade-offs.

This approach attempts to solve the problem with a single greedy modification after an initial shortest path calculation. The idea is to find the shortest possible path by setting all modifiable edges to weight 1. If this minimum distance is already greater than the target, it's impossible. Otherwise, we calculate the deficit and add it to the weight of a single modifiable edge on the shortest path. This is a simple and fast approach, but its major drawback is its lack of correctness. By increasing the weight of one path, we might inadvertently make another path the new shortest one.

Algorithm

Set all edge weights of -1 to their minimum possible value, 1.
Run Dijkstra's algorithm from the source node to find the shortest path to the destination.
Let the shortest distance found be d.
If d > target, it's impossible to reach the target, as we've already used the minimum possible weights. Return an empty array.
If d == target, we have found a valid modification. Return the edges array with all -1 weights replaced by 1.
If d < target, we need to increase the shortest path's length. Calculate the difference diff = target - d.
Find any shortest path from source to destination.
Traverse this path and find the first edge (u, v) that originally had a weight of -1.
Greedily add the entire diff to this edge's weight. Its new weight becomes 1 + diff.
All other -1 edges remain with a weight of 1.
Return the modified edges array.

Walkthrough

The algorithm begins by being optimistic: it assumes the best-case scenario where all modifiable edges (-1) are assigned the smallest possible positive integer weight, which is 1. With this setup, it computes the shortest distance from source to destination using Dijkstra's algorithm. Let's call this distance d_min.

If d_min is greater than target, we can immediately conclude that it's impossible to achieve the target distance. Any other valid assignment would involve weights greater than or equal to 1, leading to a shortest path of at least d_min.

If d_min is exactly equal to target, we've found a solution. We can return the edges with all -1s changed to 1.

The interesting case is when d_min < target. The greedy strategy is to take the diff = target - d_min and add it to one of the modifiable edges on the shortest path found. The hope is that this path's length becomes target, and it remains the shortest path overall. However, this is not guaranteed, as another path might now be shorter.

1// This is a conceptual illustration of the flawed greedy approach.2// It is not a complete and correct solution.3class Solution {4    public int[][] modifiedGraphEdges(int n, int[][] edges, int source, int destination, int target) {5        // Step 1: Set all -1 weights to 16        for (int[] edge : edges) {7            if (edge[2] == -1) {8                edge[2] = 1;9            }10        }11 12        // Step 2 & 3: Run Dijkstra to find shortest path d13        long d = dijkstra(n, edges, source, destination);14 15        // Step 4: d > target16        if (d > target) {17            return new int[0][0];18        }19 20        // Step 5: d == target21        if (d == target) {22            return edges;23        }24 25        // Step 6, 7, 8, 9: d < target, greedy modification26        long diff = target - d;27        for (int[] edge : edges) {28            // This check is flawed because we don't know if this edge was on the shortest path.29            // A proper implementation would require path reconstruction.30            // Assuming we found a -1 edge on the path that was originally -1.31            // The logic to identify which edges were originally -1 is missing here for brevity.32            // Let's say we have a way to identify them.33            if (isOriginalMinusOne(edge)) { // Pseudocode34                edge[2] += diff;35                // After modifying one, we would break and return.36                return edges; 37            }38        }39        40        return new int[0][0]; // Should not be reached if a -1 edge exists on path41    }42 43    private long dijkstra(int n, int[][] edges, int source, int destination) {44        // Standard Dijkstra implementation45        // ... returns shortest distance46        return -1; // Placeholder47    }48 49    private boolean isOriginalMinusOne(int[] edge) {50        // Helper to check if an edge was originally -151        return false; // Placeholder52    }53}

Complexity

Time

O(E + V log V) for a single run of Dijkstra's algorithm with a priority queue.

Space

O(V + E), where V is the number of nodes and E is the number of edges, for storing the graph and Dijkstra's data structures.

Trade-offs

Pros

Simple to understand and implement.
Very fast, requiring only one run of Dijkstra's algorithm.

Cons

This approach is fundamentally flawed and will fail for many test cases.
The greedy choice of adding the entire difference to a single edge on one shortest path does not guarantee that this path remains the shortest. Another path, unaffected by this weight change, might become the new shortest path, resulting in a final distance less than the target.

This approach refines the flawed greedy strategy by iteratively correcting the edge weights. Instead of performing a single modification and hoping for the best, it enters a loop. In each iteration, it finds the current shortest path. If this path is shorter than the target, it increases the weight of a modifiable edge on this path to make its length equal to the target. Then, it re-calculates the shortest path for the entire graph. This process repeats until the overall shortest path from source to destination equals the target. This ensures that at each step, we are addressing the path that is preventing us from meeting the target, guaranteeing a correct solution if one exists.

Algorithm

Create a copy of the edges or a way to track which edges were originally -1.
In the main edges array, change all -1 weights to 1.
Run Dijkstra's algorithm from source to find the shortest distance d to destination.
If at this point d > target, it's impossible. Return an empty array.
Enter a loop that continues as long as d < target: a. Calculate the needed increment: diff = target - d. b. Reconstruct the current shortest path from source to destination using parent pointers from the last Dijkstra run. c. Traverse this path to find the first edge (u, v) that was originally -1. d. If no such edge is found on the path, it means the shortest path's length is fixed and less than target. It's impossible to modify it. Return an empty array. e. Increase the weight of this edge (u, v) by diff. This makes this path's length exactly target. f. Run Dijkstra's algorithm again to find the new shortest distance d. The distance d will not decrease.
Once the loop terminates, d must be equal to target. Return the modified edges array.

Walkthrough

This iterative algorithm provides a robust way to find a valid weight assignment. It works by repeatedly identifying and lengthening the shortest path until it meets the target.

First, all modifiable edges (weight -1) are tentatively set to 1. We compute the shortest path distance, d. If d > target, no solution exists.

If d < target, we enter a loop. The goal of each iteration is to increase the current shortest path's length. We calculate diff = target - d. We then find one of the current shortest paths and pick a modifiable edge on it. We increase this edge's weight by diff. This strategic increase ensures that this particular path now has a length of target.

However, another path might now be the shortest. So, we run Dijkstra's again to find the new shortest distance, d'. Since we only increased an edge weight, d' will be greater than or equal to d. This process continues. In each step, the shortest distance d gets closer to target. The loop terminates when d finally equals target.

If at any point the current shortest path contains no modifiable edges and its length is less than target, we are stuck and no solution is possible.

1import java.util.*;2 3class Solution {4    public int[][] modifiedGraphEdges(int n, int[][] edges, int source, int destination, int target) {5        List<int[]>[] adj = new ArrayList[n];6        for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();7        8        boolean[] isNegative = new boolean[edges.length];9        for (int i = 0; i < edges.length; i++) {10            int u = edges[i][0], v = edges[i][1], w = edges[i][2];11            if (w == -1) {12                isNegative[i] = true;13                edges[i][2] = 1;14            }15            adj[u].add(new int[]{v, edges[i][2], i});16            adj[v].add(new int[]{u, edges[i][2], i});17        }18 19        long[] dist = new long[n];20        int[] parent = new int[n];21        int[] parentEdgeIndex = new int[n];22 23        long d = runDijkstra(n, adj, source, destination, dist, parent, parentEdgeIndex);24 25        if (d > target) {26            return new int[0][0];27        }28 29        if (d < target) {30            while (d < target) {31                int curr = destination;32                boolean found = false;33                while (curr != source) {34                    int p = parent[curr];35                    int edgeIndex = parentEdgeIndex[curr];36                    if (isNegative[edgeIndex]) {37                        long diff = target - d;38                        edges[edgeIndex][2] += diff;39                        // Update adjacency list as well40                        for(int[] edge : adj[p]) {41                            if(edge[2] == edgeIndex) edge[1] += diff;42                        }43                        for(int[] edge : adj[curr]) {44                            if(edge[2] == edgeIndex) edge[1] += diff;45                        }46                        found = true;47                        break;48                    }49                    curr = p;50                }51 52                if (!found) {53                    // Shortest path has no -1 edges and is < target54                    return new int[0][0];55                }56 57                d = runDijkstra(n, adj, source, destination, dist, parent, parentEdgeIndex);58                if (d > target) {59                    // This can happen if we add too much weight and another path becomes shorter60                    // but the path we modified is now much longer than target.61                    // The new shortest path could be > target.62                    // In this specific problem logic, this implies impossibility.63                    return new int[0][0];64                }65            }66        }67        68        // Final check if d is not exactly target69        if (d != target) return new int[0][0];70 71        return edges;72    }73 74    private long runDijkstra(int n, List<int[]>[] adj, int source, int destination, long[] dist, int[] parent, int[] parentEdgeIndex) {75        Arrays.fill(dist, Long.MAX_VALUE);76        Arrays.fill(parent, -1);77        Arrays.fill(parentEdgeIndex, -1);78        dist[source] = 0;79 80        PriorityQueue<long[]> pq = new PriorityQueue<>(Comparator.comparingLong(a -> a[1]));81        pq.offer(new long[]{source, 0});82 83        while (!pq.isEmpty()) {84            long[] curr = pq.poll();85            int u = (int) curr[0];86            long d = curr[1];87 88            if (d > dist[u]) continue;89            if (u == destination) return d;90 91            for (int[] edge : adj[u]) {92                int v = edge[0];93                int w = edge[1];94                int edgeIdx = edge[2];95                if (dist[u] + w < dist[v]) {96                    dist[v] = dist[u] + w;97                    parent[v] = u;98                    parentEdgeIndex[v] = edgeIdx;99                    pq.offer(new long[]{v, dist[v]});100                }101            }102        }103        return dist[destination];104    }105}

Complexity

Time

O(C * (E + V log V)), where `C` is the number of modifiable edges, `V` is the number of nodes, and `E` is the number of edges. The `while` loop runs at most `C` times, and each iteration is dominated by Dijkstra's algorithm.

Space

O(V + E) to store the graph, parent pointers, and other data for Dijkstra's algorithm.

Trade-offs

Pros

Guaranteed to find a correct solution if one exists.
The logic is robust and handles complex graph structures correctly by re-evaluating the global shortest path at each step.

Cons

The main drawback is the performance. In the worst case, it might run Dijkstra's algorithm many times.
The number of iterations is bounded by the number of modifiable edges, which can be large.

Solutions

Solution

1class Solution {2private3  final int inf = 2000000000;4public5  int[][] modifiedGraphEdges(int n, int[][] edges, int source, int destination,6                             int target) {7    long d = dijkstra(edges, n, source, destination);8    if (d < target) {9      return new int[0][];10    }11    boolean ok = d == target;12    for (var e : edges) {13      if (e[2] > 0) {14        continue;15      }16      if (ok) {17        e[2] = inf;18        continue;19      }20      e[2] = 1;21      d = dijkstra(edges, n, source, destination);22      if (d <= target) {23        ok = true;24        e[2] += target - d;25      }26    }27    return ok ? edges : new int[0][];28  }29private30  long dijkstra(int[][] edges, int n, int src, int dest) {31    int[][] g = new int[n][n];32    long[] dist = new long[n];33    Arrays.fill(dist, inf);34    dist[src] = 0;35    for (var f : g) {36      Arrays.fill(f, inf);37    }38    for (var e : edges) {39      int a = e[0], b = e[1], w = e[2];40      if (w == -1) {41        continue;42      }43      g[a][b] = w;44      g[b][a] = w;45    }46    boolean[] vis = new boolean[n];47    for (int i = 0; i < n; ++i) {48      int k = -1;49      for (int j = 0; j < n; ++j) {50        if (!vis[j] && (k == -1 || dist[k] > dist[j])) {51          k = j;52        }53      }54      vis[k] = true;55      for (int j = 0; j < n; ++j) {56        dist[j] = Math.min(dist[j], dist[k] + g[k][j]);57      }58    }59    return dist[dest];60  }61}

1using ll = long long ; const int inf = 2e9 ; class Solution { public: vector < vector < int >> modifiedGraphEdges ( int n , vector < vector < int >>& edges , int source , int destination , int target ) { ll d = dijkstra ( edges , n , source , destination ); if ( d < target ) { return {}; } bool ok = d == target ; for ( auto & e : edges ) { if ( e [ 2 ] > 0 ) { continue ; } if ( ok ) { e [ 2 ] = inf ; continue ; } e [ 2 ] = 1 ; d = dijkstra ( edges , n , source , destination ); if ( d <= target ) { ok = true ; e [ 2 ] += target - d ; } } return ok ? edges : vector < vector < int >> {}; } ll dijkstra ( vector < vector < int >>& edges , int n , int src , int dest ) { ll g [ n ][ n ]; ll dist [ n ]; bool vis [ n ]; for ( int i = 0 ; i < n ; ++ i ) { fill ( g [ i ], g [ i ] + n , inf ); dist [ i ] = inf ; vis [ i ] = false ; } dist [ src ] = 0 ; for ( auto & e : edges ) { int a = e [ 0 ], b = e [ 1 ], w = e [ 2 ]; if ( w == - 1 ) { continue ; } g [ a ][ b ] = w ; g [ b ][ a ] = w ; } for ( int i = 0 ; i < n ; ++ i ) { int k = - 1 ; for ( int j = 0 ; j < n ; ++ j ) { if ( ! vis [ j ] && ( k == - 1 || dist [ j ] < dist [ k ])) { k = j ; } } vis [ k ] = true ; for ( int j = 0 ; j < n ; ++ j ) { dist [ j ] = min ( dist [ j ], dist [ k ] + g [ k ][ j ]); } } return dist [ dest ]; } };

1class Solution:2    def modifiedGraphEdges(self, n: int, edges: List[List[int]], source: int, destination: int, target: int) -> List[List[int]]: def dijkstra(edges: List[List[int]]) -> int: g = [[inf] * n for _ in range(n)] for a, b, w in edges: if w == - 1: continue g[a][b] = g[b][a] = w dist = [inf] * n dist[source] = 0 vis = [False] * n for _ in range(n): k = - 1 for j in range(n): if not vis[j] and (k == - 1 or dist[k] > dist[j]): k = j vis[k] = True for j in range(n): dist[j] = min(dist[j], dist[k] + g[k][j]) return dist[destination] inf = 2 * 10 ** 9 d = dijkstra(edges) if d < target: return [] ok = d == target for e in edges: if e[2] > 0: continue if ok: e[2] = inf continue e[2] = 1 d = dijkstra(edges) if d <= target: ok = True e[2] += target - d return edges if ok else []

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem