# Modify Graph Edge Weights
**Difficulty:** HARD
[External](https://leetcode.com/problems/modify-graph-edge-weights)
Canonical: https://scaleengineer.com/dsa/problems/modify-graph-edge-weights
**Algorithms:** [Shortest Path](https://scaleengineer.com/algorithms/shortest-path)
**Data structures:** Heap (Priority Queue), Graph
---
## Problem
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] = [ai, bi, wi]` indicates that there is an edge between nodes `ai` and `bi` with weight `wi`.

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

Your task is to modify **all edges** with a weight of `-1` by assigning them **positive integer values** in the range `[1, 2 * 109]` 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:**

**![](https://assets.glich.co/dsa/modify-graph-edge-weights/image0.png)**

**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:**

**![](https://assets.glich.co/dsa/modify-graph-edge-weights/image1.png)**

**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:**

**![](https://assets.glich.co/dsa/modify-graph-edge-weights/image2.png)**

**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 <= ai, bi < n`
* `wi = -1 `or `1 <= wi <= 107`
* `ai != bi`
* `0 <= source, destination < n`
* `source != destination`
* `1 <= target <= 109`
* The graph is connected, and there are no self-loops or repeated edges

# Approaches
## Flawed Greedy Approach
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.
**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.
**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.
### Explanation
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 `-1`s 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.

```java
// This is a conceptual illustration of the flawed greedy approach.
// It is not a complete and correct solution.
class Solution {
    public int[][] modifiedGraphEdges(int n, int[][] edges, int source, int destination, int target) {
        // Step 1: Set all -1 weights to 1
        for (int[] edge : edges) {
            if (edge[2] == -1) {
                edge[2] = 1;
            }
        }

        // Step 2 & 3: Run Dijkstra to find shortest path d
        long d = dijkstra(n, edges, source, destination);

        // Step 4: d > target
        if (d > target) {
            return new int[0][0];
        }

        // Step 5: d == target
        if (d == target) {
            return edges;
        }

        // Step 6, 7, 8, 9: d < target, greedy modification
        long diff = target - d;
        for (int[] edge : edges) {
            // This check is flawed because we don't know if this edge was on the shortest path.
            // A proper implementation would require path reconstruction.
            // Assuming we found a -1 edge on the path that was originally -1.
            // The logic to identify which edges were originally -1 is missing here for brevity.
            // Let's say we have a way to identify them.
            if (isOriginalMinusOne(edge)) { // Pseudocode
                edge[2] += diff;
                // After modifying one, we would break and return.
                return edges; 
            }
        }
        
        return new int[0][0]; // Should not be reached if a -1 edge exists on path
    }

    private long dijkstra(int n, int[][] edges, int source, int destination) {
        // Standard Dijkstra implementation
        // ... returns shortest distance
        return -1; // Placeholder
    }

    private boolean isOriginalMinusOne(int[] edge) {
        // Helper to check if an edge was originally -1
        return false; // Placeholder
    }
}
```
### Algorithm
1. Set all edge weights of `-1` to their minimum possible value, `1`.
2. Run Dijkstra's algorithm from the `source` node to find the shortest path to the `destination`.
3. Let the shortest distance found be `d`.
4. If `d > target`, it's impossible to reach the target, as we've already used the minimum possible weights. Return an empty array.
5. If `d == target`, we have found a valid modification. Return the `edges` array with all `-1` weights replaced by `1`.
6. If `d < target`, we need to increase the shortest path's length. Calculate the difference `diff = target - d`.
7. Find any shortest path from `source` to `destination`. 
8. Traverse this path and find the first edge `(u, v)` that originally had a weight of `-1`.
9. Greedily add the entire `diff` to this edge's weight. Its new weight becomes `1 + diff`.
10. All other `-1` edges remain with a weight of `1`.
11. Return the modified `edges` array.

## Iterative Shortest Path Lengthening
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.
**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.
**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.
### Explanation
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.

```java
import java.util.*;

class Solution {
    public int[][] modifiedGraphEdges(int n, int[][] edges, int source, int destination, int target) {
        List<int[]>[] adj = new ArrayList[n];
        for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
        
        boolean[] isNegative = new boolean[edges.length];
        for (int i = 0; i < edges.length; i++) {
            int u = edges[i][0], v = edges[i][1], w = edges[i][2];
            if (w == -1) {
                isNegative[i] = true;
                edges[i][2] = 1;
            }
            adj[u].add(new int[]{v, edges[i][2], i});
            adj[v].add(new int[]{u, edges[i][2], i});
        }

        long[] dist = new long[n];
        int[] parent = new int[n];
        int[] parentEdgeIndex = new int[n];

        long d = runDijkstra(n, adj, source, destination, dist, parent, parentEdgeIndex);

        if (d > target) {
            return new int[0][0];
        }

        if (d < target) {
            while (d < target) {
                int curr = destination;
                boolean found = false;
                while (curr != source) {
                    int p = parent[curr];
                    int edgeIndex = parentEdgeIndex[curr];
                    if (isNegative[edgeIndex]) {
                        long diff = target - d;
                        edges[edgeIndex][2] += diff;
                        // Update adjacency list as well
                        for(int[] edge : adj[p]) {
                            if(edge[2] == edgeIndex) edge[1] += diff;
                        }
                        for(int[] edge : adj[curr]) {
                            if(edge[2] == edgeIndex) edge[1] += diff;
                        }
                        found = true;
                        break;
                    }
                    curr = p;
                }

                if (!found) {
                    // Shortest path has no -1 edges and is < target
                    return new int[0][0];
                }

                d = runDijkstra(n, adj, source, destination, dist, parent, parentEdgeIndex);
                if (d > target) {
                    // This can happen if we add too much weight and another path becomes shorter
                    // but the path we modified is now much longer than target.
                    // The new shortest path could be > target.
                    // In this specific problem logic, this implies impossibility.
                    return new int[0][0];
                }
            }
        }
        
        // Final check if d is not exactly target
        if (d != target) return new int[0][0];

        return edges;
    }

    private long runDijkstra(int n, List<int[]>[] adj, int source, int destination, long[] dist, int[] parent, int[] parentEdgeIndex) {
        Arrays.fill(dist, Long.MAX_VALUE);
        Arrays.fill(parent, -1);
        Arrays.fill(parentEdgeIndex, -1);
        dist[source] = 0;

        PriorityQueue<long[]> pq = new PriorityQueue<>(Comparator.comparingLong(a -> a[1]));
        pq.offer(new long[]{source, 0});

        while (!pq.isEmpty()) {
            long[] curr = pq.poll();
            int u = (int) curr[0];
            long d = curr[1];

            if (d > dist[u]) continue;
            if (u == destination) return d;

            for (int[] edge : adj[u]) {
                int v = edge[0];
                int w = edge[1];
                int edgeIdx = edge[2];
                if (dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    parent[v] = u;
                    parentEdgeIndex[v] = edgeIdx;
                    pq.offer(new long[]{v, dist[v]});
                }
            }
        }
        return dist[destination];
    }
}
```
### Algorithm
1. Create a copy of the edges or a way to track which edges were originally `-1`.
2. In the main `edges` array, change all `-1` weights to `1`.
3. Run Dijkstra's algorithm from `source` to find the shortest distance `d` to `destination`.
4. If at this point `d > target`, it's impossible. Return an empty array.
5. 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.
6. Once the loop terminates, `d` must be equal to `target`. Return the modified `edges` array.

# Solutions
### Java

```java
class Solution {
private
  final int inf = 2000000000;
public
  int[][] modifiedGraphEdges(int n, int[][] edges, int source, int destination,
                             int target) {
    long d = dijkstra(edges, n, source, destination);
    if (d < target) {
      return new int[0][];
    }
    boolean ok = d == target;
    for (var 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 : new int[0][];
  }
private
  long dijkstra(int[][] edges, int n, int src, int dest) {
    int[][] g = new int[n][n];
    long[] dist = new long[n];
    Arrays.fill(dist, inf);
    dist[src] = 0;
    for (var f : g) {
      Arrays.fill(f, inf);
    }
    for (var e : edges) {
      int a = e[0], b = e[1], w = e[2];
      if (w == -1) {
        continue;
      }
      g[a][b] = w;
      g[b][a] = w;
    }
    boolean[] vis = new boolean[n];
    for (int i = 0; i < n; ++i) {
      int k = -1;
      for (int j = 0; j < n; ++j) {
        if (!vis[j] && (k == -1 || dist[k] > dist[j])) {
          k = j;
        }
      }
      vis[k] = true;
      for (int j = 0; j < n; ++j) {
        dist[j] = Math.min(dist[j], dist[k] + g[k][j]);
      }
    }
    return dist[dest];
  }
}

```

### CPP

```cpp
using 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 ]; } };
```

### Python

```python
class Solution:
    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 []

```