2699. Modify Graph Edge Weights - Solution

The 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] = [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

Approach overview

Problem Overview: You are given an undirected graph where some edges have weight -1. Replace those weights with positive values so the shortest path from source to destination equals exactly target. If multiple assignments exist, return any valid graph. If it's impossible, return an empty result.

Approach 1: Dijkstra with Prioritization for -1 Edges (O(m log n) time, O(n + m) space)

This approach treats -1 edges as adjustable during the shortest path computation. Run shortest path using Dijkstra while initially assigning minimal values to unknown edges. When the path distance is smaller than the target, increase weights of selected -1 edges along the candidate path so the final distance matches the target exactly. A priority queue ensures nodes are processed in increasing distance order. The key insight: delay committing final weights until you know which edges affect the optimal path.

Approach 2: Binary Search on Edge Weights with Dijkstra (O(k * m log n) time, O(n + m) space)

Replace each -1 edge with a candidate weight and verify the resulting shortest path using Dijkstra. Instead of guessing blindly, binary search the value range for one adjustable edge while keeping others minimal. Each check runs a shortest path computation on the graph. If the path length becomes larger than the target, reduce the candidate weight; otherwise increase it. This isolates the exact value that makes the path length equal the target.

Approach 3: Dijkstra's Algorithm with Binary Search (O(k * m log n) time, O(n + m) space)

This variant focuses on gradually enabling -1 edges. First run Dijkstra ignoring unknown edges to determine the baseline distance. If it already equals the target, assign very large weights to unused -1 edges. Otherwise, iteratively activate them with small weights and run Dijkstra again. Binary search determines the precise adjustment needed so the shortest path becomes exactly target. This works well when the number of unknown edges is limited.

Approach 4: Iterative Adjustment with BFS (O(k * (n + m)) time, O(n + m) space)

When weights are treated incrementally, you can run repeated BFS-style relaxations while modifying -1 edges. Start by assigning them the smallest allowed value. If the computed path is too short, incrementally increase selected edges until the distance equals the target. This approach avoids heavy priority queue operations but may require multiple passes across the graph. It is easier to implement but less efficient for dense graphs.

Recommended for interviews: Dijkstra with prioritization for -1 edges. It demonstrates strong understanding of weighted graph traversal and dynamic edge adjustment. Brute-force or iterative checks show the core idea, but the optimized Dijkstra-based approach proves you can control shortest-path constraints while maintaining O(m log n) complexity.

Approach 1: Approach 1: Dijkstra's Algorithm with Binary Search

In this approach, we use Dijkstra's algorithm to calculate the shortest path in the graph. The edges with initial weight -1 are considered candidates for modification. We apply binary search to find the appropriate weights for these edges, constraining the path length from source to destination to be equal to the target.

For edges with weight -1, we replace them with a large number initially (greater than the maximum possible path) and refine these weights using binary search to converge on the optimal configuration.

Python

from heapq import heappop, heappush

def dijkstra(graph, n, src):
    dist = [float('inf')] * n
    dist[src] = 0
    heap = [(0, src)]
    while heap:
        d, u = heappop(heap)
        if d > dist[u]:
            continue
        for v, weight in graph[u]:
            if dist[v] > dist[u] + weight:
                dist[v] = dist[u] + weight
                heappush(heap, (dist[v], v))
    return dist

def modify_graph_edges(n, edges, source, destination, target):
    def create_graph(weight_delta=0):
        graph = [[] for _ in range(n)]
        for u, v, w in edges:
            if w != -1:
                graph[u].append((v, w))
                graph[v].append((u, w))
            else:
                graph[u].append((v, weight_delta))
                graph[v].append((u, weight_delta))
        return graph

    left, right = 1, 2 * 10**9
    result = []

    while left <= right:
        mid = (left + right) // 2
        graph = create_graph(mid)
        dist = dijkstra(graph, n, source)

        if dist[destination] < target:
            left = mid + 1
        else:
            if dist[destination] == target:
                result = [(u, v, (mid if w == -1 else w)) for u, v, w in edges]
            right = mid - 1

    return result if result else []

# Example usage:
n = 4
edges = [[1,0,4],[1,2,3],[2,3,5],[0,3,-1]]
source = 0
destination = 2
target = 6
print(modify_graph_edges(n, edges, source, destination, target))

This solution defines a function to apply Dijkstra's algorithm and uses binary search to refine the weights of -1 edges to achieve the target shortest path. The graph is constructed such that each edge weight is initially the binary search mid value when unknown (-1). We update the search bounds based on whether the constructed path is less than, equal to, or greater than the target.

Complexity

Time Complexity: O(E * log(V) * log(W)), where E is the number of edges, V is the number of vertices, and W is the weight range (binary search range).

Space Complexity: O(V + E), mainly for storing the graph structure and distances.

Try this approach in the editor

Approach 2: Approach 2: Iterative Adjustment with BFS

This alternative approach leverages an iterative process to adjust edge weights. Starting with a breadth-first search (BFS)-like traversal, we replace unknown weights and check whether the current path meets or exceeds the target. Adjustments are made iteratively until the desired path length is achieved.

Java

import java.util.*;

public class GraphSolution {
    private static final int INF = Integer.MAX_VALUE;

    public List<int[]> adjustGraphEdges(int n, int[][] edges, int source, int destination, int target) {
        int left = 1, right = 2_000_000_000;
        int[] result = null;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            int[] distances = bfsWithWeight(n, edges, source, mid);

            if (distances[destination] < target) {
                left = mid + 1;
            } else {
                if (distances[destination] == target) {
                    result = replaceWeights(edges, mid);
                }
                right = mid - 1;
            }
        }

        return result != null ? Arrays.asList(result) : new ArrayList<>();
    }

    private int[] bfsWithWeight(int n, int[][] edges, int source, int weight) {
        List<int[]>[] graph = buildGraph(n, edges, weight);
        int[] dist = new int[n];
        Arrays.fill(dist, INF);
        dist[source] = 0;
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(source);
        
        while (!queue.isEmpty()) {
            int u = queue.poll();
            for (int[] adj : graph[u]) {
                int v = adj[0], w = adj[1];
                if (dist[v] > dist[u] + w) {
                    dist[v] = dist[u] + w;
                    queue.offer(v);
                }
            }
        }

        return dist;
    }

    private List<int[]>[] buildGraph(int n, int[][] edges, int weight) {
        List<int[]>[] graph = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int[] edge : edges) {
            int a = edge[0], b = edge[1], w = edge[2] == -1 ? weight : edge[2];
            graph[a].add(new int[]{b, w});
            graph[b].add(new int[]{a, w});
        }
        return graph;
    }

    private int[] replaceWeights(int[][] edges, int newWeight) {
        for (int[] edge : edges) {
            if (edge[2] == -1) {
                edge[2] = newWeight;
            }
        }
        return Arrays.stream(edges).flatMapToInt(Arrays::stream).toArray();
    }

    public static void main(String[] args) {
        GraphSolution solution = new GraphSolution();
        int n = 4;
        int[][] edges = {{1,0,4},{1,2,3},{2,3,5},{0,3,-1}};
        int source = 0;
        int destination = 2;
        int target = 6;
        List<int[]> result = solution.adjustGraphEdges(n, edges, source, destination, target);
        System.out.println(result);
    }
}

This Java solution employs a modified BFS combined with binary search logic to iteratively refine edge weights. The BFS adaptation is used to assess the impact of current estimations on the maximum path length. Adjustments cease when we obtain the desired critical path or exhaust search options.

Complexity

Time Complexity: O(E * V * log(W)), where E is the number of edges, V is the number of vertices, and W is the binary search range for weights.

Space Complexity: O(V + E) for the graph representation and distance tracking.

Try this approach in the editor

Approach 3: Binary Search on Edge Weights

In this approach, we use binary search to determine the appropriate weights to assign to edges with initial weight of -1 such that the shortest path from the source to the destination is equal to the target. The idea is to repeatedly apply Dijkstra's algorithm with modified weights until we find the exact configuration which results in the shortest path distance equal to the target.

Python

# Python solution implementing binary search on edge weights
from typing import List

class Edge:
    def __init__(self, u, v, w):
        self.u = u
        self.v = v
        self.w = w

    def __repr__(self):
        return f'[{self.u}, {self.v}, {self.w}]'

def bellman_ford(n: int, edges: List[Edge], source: int) -> List[int]:
    dist = [float('inf')] * n
    dist[source] = 0

    for _ in range(n - 1):
        for edge in edges:
            if dist[edge.u] != float('inf') and dist[edge.u] + edge.w < dist[edge.v]:
                dist[edge.v] = dist[edge.u] + edge.w

    return dist

def modify_graph_edges(n: int, edge_list: List[List[int]], source: int, destination: int, target: int) -> List[List[int]]:
    edges = [Edge(u, v, w) for u, v, w in edge_list]
    left, right = 1, 2 * 10**9

    while left < right:
        # Modify edges
        mid = (left + right) // 2
        for edge in edges:
            if edge.w == -1:
                edge.w = mid

        dist = bellman_ford(n, edges, source)

        if dist[destination] > target:
            right = mid
        elif dist[destination] < target:
            left = mid + 1
        else:
            return [[edge.u, edge.v, edge.w] for edge in edges]

    return []

# Example usage
n = 4
edge_list = [[1,0,4],[1,2,3],[2,3,5],[0,3,-1]]
source = 0
# Python Test
print(modify_graph_edges(n, edge_list, source, 2, 6))

Java

// Java solution implementing binary search on edge weights
import java.util.*;

class Edge {
    int u, v, w;
    Edge(int u, int v, int w) {
        this.u = u;
        this.v = v;
        this.w = w;
    }
}

public class GraphModifier {
    public static void modifyGraphEdges(int n, List<Edge> edges, int source, int destination, int target) {
        int left = 1, right = 2 * (int) 1e9;
        List<Integer> dist = new ArrayList<>(Collections.nCopies(n, Integer.MAX_VALUE));

        while (left < right) {
            int mid = left + (right - left) / 2;

            edges.forEach(edge -> {
                if (edge.w == -1) edge.w = mid;
            });

            if (!bellmanFord(n, edges, source, dist)) {
                right = mid;
                continue;
            }

            if (dist.get(destination) > target) {
                right = mid;
            } else if (dist.get(destination) < target) {
                left = mid + 1;
            } else {
                edges.forEach(edge -> {
                    System.out.printf("[%d, %d, %d]\n", edge.u, edge.v, edge.w);
                });
                return;
            }
        }
        System.out.println("[]");
    }

    private static boolean bellmanFord(int n, List<Edge> edges, int source, List<Integer> dist) {
        Collections.fill(dist, Integer.MAX_VALUE);
        dist.set(source, 0);
        for (int i = 0; i < n - 1; ++i) {
            for (Edge edge : edges) {
                if (dist.get(edge.u) != Integer.MAX_VALUE && dist.get(edge.u) + edge.w < dist.get(edge.v)) {
                    dist.set(edge.v, dist.get(edge.u) + edge.w);
                }
            }
        }
        return true;
    }

    public static void main(String[] args) {
        int n = 4;
        List<Edge> edges = Arrays.asList(new Edge(1, 0, 4), new Edge(1, 2, 3), new Edge(2, 3, 5), new Edge(0, 3, -1));
        int source = 0;
        int destination = 2;
        int target = 6;
        modifyGraphEdges(n, edges, source, destination, target);
    }
}

C++

// C++ solution implementing binary search on edge weights
#include <iostream>
#include <vector>
#include <limits>

using namespace std;

class Edge {
public:
    int u, v, w;
    Edge(int u_, int v_, int w_) : u(u_), v(v_), w(w_) {}
};

bool bellmanFord(int n, vector<Edge> &edges, int source, vector<int> &dist) {
    dist.assign(n, INT_MAX);
    dist[source] = 0;
    for (int i = 0; i < n - 1; ++i) {
        for (auto &edge : edges) {
            if (dist[edge.u] != INT_MAX && dist[edge.u] + edge.w < dist[edge.v]) {
                dist[edge.v] = dist[edge.u] + edge.w;
            }
        }
    }
    return true;
}

void modifyGraphEdges(int n, vector<Edge> &edges, int source, int destination, int target) {
    vector<int> dist;

    int left = 1, right = 2 * 1e9;
    while (left < right) {
        int mid = left + (right - left) / 2;

        for (auto &edge : edges) {
            if (edge.w == -1) edge.w = mid;
        }

        if (!bellmanFord(n, edges, source, dist)) {
            right = mid;
            continue;
        }

        if (dist[destination] > target) {
            right = mid;
        } else if (dist[destination] < target) {
            left = mid + 1;
        } else {
            for (auto &edge : edges) {
                cout << "[" << edge.u << ", " << edge.v << ", " << edge.w << "]\n";
            }
            return;
        }
    }
    cout << "[]\n";
}

int main() {
    int n = 4;
    vector<Edge> edges = {{1,0,4},{1,2,3},{2,3,5},{0,3,-1}};
    int source = 0;
    int destination = 2;
    int target = 6;
    modifyGraphEdges(n, edges, source, destination, target);
    return 0;
}

JavaScript

// JavaScript solution implementing binary search on edge weights
class Edge {
    constructor(u, v, w) {
        this.u = u;
        this.v = v;
        this.w = w;
    }
}

function bellmanFord(n, edges, source) {
    let dist = Array(n).fill(Infinity);
    dist[source] = 0;

    for (let i = 0; i < n - 1; i++) {
        for (let edge of edges) {
            if (dist[edge.u] !== Infinity && dist[edge.u] + edge.w < dist[edge.v]) {
                dist[edge.v] = dist[edge.u] + edge.w;
            }
        }
    }
    return dist;
}

function modifyGraphEdges(n, edgeList, source, destination, target) {
    let edges = edgeList.map(([u, v, w]) => new Edge(u, v, w));
    let left = 1, right = 2 * 1e9;

    while (left < right) {
        let mid = Math.floor((left + right) / 2);

        for (let edge of edges) {
            if (edge.w === -1) edge.w = mid;
        }

        let dist = bellmanFord(n, edges, source);

        if (dist[destination] > target) {
            right = mid;
        } else if (dist[destination] < target) {
            left = mid + 1;
        } else {
            return edges.map(edge => [edge.u, edge.v, edge.w]);
        }
    }
    return [];
}

// Example usage
let n = 4;
let edgeList = [[1,0,4],[1,2,3],[2,3,5],[0,3,-1]];
let source = 0;
let destination = 2;
let target = 6;
console.log(modifyGraphEdges(n, edgeList, source, destination, target));

// C solution implementing binary search on edge weights
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <stdbool.h>

#define MAXN 100
#define INF INT_MAX

typedef struct {
    int u, v, w;
} Edge;

int min(int a, int b) {
    return a < b ? a : b;
}

bool bellmanFord(int n, Edge edges[], int edgesSize, int source, int *dist) {
    for (int i = 0; i < n; i++) dist[i] = INF;
    dist[source] = 0;
    
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < edgesSize; j++) {
            int u = edges[j].u, v = edges[j].v, w = edges[j].w;
            if (dist[u] != INF && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
            }
        }
    }
    return true;
}

void modifyGraphEdges(int n, Edge edges[], int edgesSize, int source, int destination, int target) {
    int dist[MAXN];
    if (!bellmanFord(n, edges, edgesSize, source, dist)) {
        printf("[]\n");
        return;
    }

    int left = 1, right = 2 * 1000000000;
    while (left < right) {
        int mid = left + (right - left) / 2;

        // Modify all -1 weights to mid
        for (int i = 0; i < edgesSize; i++) {
            if (edges[i].w == -1) edges[i].w = mid;
        }

        if (!bellmanFord(n, edges, edgesSize, source, dist)) {
            right = mid;
            continue;
        }
        if (dist[destination] > target) {
            right = mid;
        } else if (dist[destination] < target) {
            left = mid + 1;
        } else {
            printf("[Modification possible]\n");
            for (int i = 0; i < edgesSize; i++)
                printf("[%d, %d, %d]\n", edges[i].u, edges[i].v, edges[i].w);
            return;
        }
    }
    printf("[]\n");
}

int main() {
    int n = 4;
    Edge edges[] = {{1,0,4},{1,2,3},{2,3,5},{0,3,-1}};
    int edgesSize = sizeof(edges) / sizeof(edges[0]);
    int source = 0;
    int destination = 2;
    int target = 6;
    modifyGraphEdges(n, edges, edgesSize, source, destination, target);
    return 0;
}

// C# solution implementing binary search on edge weights
using System;
using System.Collections.Generic;

class Edge {
    public int U, V, W;
    public Edge(int u, int v, int w) {
        U = u; V = v; W = w;
    }
}

class GraphModifier {
    public static void ModifyGraphEdges(int n, List<Edge> edges, int source, int destination, int target) {
        int left = 1, right = 2 * 1000000000;
        var dist = new int[n];

        while (left < right) {
            int mid = left + (right - left) / 2;
            foreach (var edge in edges) {
                if (edge.W == -1) edge.W = mid;
            }

            if (!BellmanFord(n, edges, source, dist)) {
                right = mid;
                continue;
            }

            if (dist[destination] > target) {
                right = mid;
            } else if (dist[destination] < target) {
                left = mid + 1;
            } else {
                foreach (var edge in edges) {
                    Console.WriteLine($"[{edge.U}, {edge.V}, {edge.W}]");
                }
                return;
            }
        }
        Console.WriteLine("[]");
    }

    private static bool BellmanFord(int n, List<Edge> edges, int source, int[] dist) {
        Array.Fill(dist, int.MaxValue);
        dist[source] = 0;

        for (int i = 0; i < n - 1; ++i) {
            foreach (var edge in edges) {
                if (dist[edge.U] != int.MaxValue && dist[edge.U] + edge.W < dist[edge.V]) {
                    dist[edge.V] = dist[edge.U] + edge.W;
                }
            }
        }
        return true;
    }

    public static void Main() {
        int n = 4;
        List<Edge> edges = new List<Edge> { new Edge(1, 0, 4), new Edge(1, 2, 3), new Edge(2, 3, 5), new Edge(0, 3, -1) };
        int source = 0;
        int destination = 2;
        int target = 6;
        ModifyGraphEdges(n, edges, source, destination, target);
    }
}

In this Python solution, we encapsulate edges within an Edge class for clarity. Binary search is used to identify optimal -1 replacements. Each pass attempts Bellman-Ford to fetch shortest paths, comparing against the target value iteratively.

Complexity

Time Complexity: O(VE), for Bellman-Ford's method dynamics integrated into the binary search.
Space Complexity: O(V), storing initial distances as necessary.

Try this approach in the editor

Approach 4: Dijkstra with Prioritization for -1 Edges

This approach leverages Dijkstra's algorithm to calculate the shortest path in the graph with a priority queue. We prioritize paths through existing edges first, checking if adjustments can achieve the target path length. It continuously updates the priority to cover edges that were initially marked with -1 with minimal adjustments. The logic attempts to find if a series of replacements can equate the length of the required path to target.

Python

# Python solution using Dijkstra and prioritizing -1 edges
import heapq

class Edge:
    def __init__(self, to, weight):
        self.to = to
        self.weight = weight

class GraphEdge:
    def __init__(self, u, v, w):
        self.u = u
        self.v = v
        self.w = w

    def __repr__(self):
        return f'[{self.u}, {self.v}, {self.w}]'


def dijkstra(n, graph, source):
    dist = [float('inf')] * n
    dist[source] = 0

    pq = [(0, source)]  # (distance, vertex)

    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue
        for edge in graph[u]:
            if dist[u] + edge.weight < dist[edge.to]:
                dist[edge.to] = dist[u] + edge.weight
                heapq.heappush(pq, (dist[edge.to], edge.to))

    return dist


def modify_graph_edges(n, edge_list, source, destination, target):
    edges = [GraphEdge(u, v, w) for u, v, w in edge_list]
    graph = [[] for _ in range(n)]
    for edge in edges:
        if edge.w != -1:
            graph[edge.u].append(Edge(edge.v, edge.w))
            graph[edge.v].append(Edge(edge.u, edge.w))

    dist = dijkstra(n, graph, source)
    path_length = dist[destination]

    # Attempt to set initial unmodified path to target by general shifts
    if path_length == target:
        for edge in edges:
            if edge.w == -1:
                edge.w = 1
    else:
        for edge in edges:
            if edge.w == -1:
                edge.w = target - path_length
                graph[edge.u].append(Edge(edge.v, edge.w))
                graph[edge.v].append(Edge(edge.u, edge.w))
                new_dist = dijkstra(n, graph, source)
                path_length = new_dist[destination]
                if path_length == target:
                    break
                edge.w = -1

    if path_length != target:
        return []  # Impossible

    return [[edge.u, edge.v, edge.w] for edge in edges]

# Example usage
n = 4
edge_list = [[1,0,4],[1,2,3],[2,3,5],[0,3,-1]]
source = 0
destination = 2
target = 6
print(modify_graph_edges(n, edge_list, source, destination, target))

Java

// Java solution using Dijkstra and prioritizing -1 edges
import java.util.*;

class Edge {
    int to, weight;
    Edge(int to, int weight) {
        this.to = to;
        this.weight = weight;
    }
}

class GraphEdge {
    int u, v, w;
    GraphEdge(int u, int v, int w) {
        this.u = u,
        this.v = v,
        this.w = w;
    }
}

public class ModifyGraphEdges {

    public static int dijkstra(int n, List<List<Edge>> graph, int source, int destination) {
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[source] = 0;

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

        while (!pq.isEmpty()) {
            int[] curr = pq.poll();
            int d = curr[0], u = curr[1];
            if (d != dist[u])
                continue;

            for (Edge edge : graph.get(u)) {
                if (dist[u] + edge.weight < dist[edge.to]) {
                    dist[edge.to] = dist[u] + edge.weight;
                    pq.offer(new int[]{dist[edge.to], edge.to});
                }
            }
        }
        return dist[destination];
    }

    public static void modifyGraphEdges(int n, List<GraphEdge> edges, int source, int destination, int target) {
        List<List<Edge>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++)
            graph.add(new ArrayList<>());

        for (GraphEdge e : edges) {
            if (e.w != -1) {
                graph.get(e.u).add(new Edge(e.v, e.w));
                graph.get(e.v).add(new Edge(e.u, e.w));
            }
        }

        int pathLength = dijkstra(n, graph, source, destination);

        if (pathLength == target) {
            for (GraphEdge e : edges) 
                if (e.w == -1) e.w = 1;
        } else {
            for (GraphEdge e : edges) {
                if (e.w == -1) {
                    e.w = target - pathLength;
                    graph.get(e.u).add(new Edge(e.v, e.w));
                    graph.get(e.v).add(new Edge(e.u, e.w));
                    pathLength = dijkstra(n, graph, source, destination);
                    if (pathLength == target) break;
                    e.w = -1;
                }
            }
        }

        if (pathLength != target) {
            System.out.println("[]");
            return;
        }

        for (GraphEdge e : edges)
            System.out.printf("[%d, %d, %d]\n", e.u, e.v, e.w);
    }

    public static void main(String[] args) {
        int n = 4;
        List<GraphEdge> edges = Arrays.asList(new GraphEdge(1,0,4), new GraphEdge(1,2,3), new GraphEdge(2,3,5), new GraphEdge(0,3,-1));
        int source = 0;
        int destination = 2;
        int target = 6;
        modifyGraphEdges(n, edges, source, destination, target);
    }
}

C++

// C++ solution using Dijkstra and prioritizing -1 edges
#include <iostream>
#include <vector>
#include <queue>
#include <limits>

struct Edge {
    int to, weight;
    Edge(int t, int w) : to(t), weight(w) {}
};

struct GraphEdge {
    int u, v, w;
};

int dijkstra(int n, std::vector<std::vector<Edge>>& graph, int src, int dst) {
    std::vector<int> dist(n, INT_MAX);
    dist[src] = 0;
    std::priority_queue<std::pair<int, int>,
                        std::vector<std::pair<int, int> >,
                        std::greater<std::pair<int, int> > > pq;
    pq.emplace(0, src);

    while (!pq.empty()) {
        int d = pq.top().first;
        int u = pq.top().second;
        pq.pop();

        if (d != dist[u]) continue;

        for (auto &e : graph[u]) {
            if (dist[u] + e.weight < dist[e.to]) {
                dist[e.to] = dist[u] + e.weight;
                pq.emplace(dist[e.to], e.to);
            }
        }
    }
    return dist[dst];
}

void modifyGraphEdges(int n, std::vector<GraphEdge>& edges, int source, int destination, int target) {
    std::vector<std::vector<Edge>> graph(n);
    for (const auto& e : edges) {
        if (e.w != -1) {
            graph[e.u].emplace_back(e.v, e.w);
            graph[e.v].emplace_back(e.u, e.w);
        }
    }

    int path_length = dijkstra(n, graph, source, destination);

    if (path_length == target) {
        for (auto& e : edges) {
            if (e.w == -1) e.w = 1;
        }
    } else {
        for (auto& e : edges) {
            if (e.w == -1) {
                e.w = target - path_length;
                graph[e.u].emplace_back(e.v, e.w);
                graph[e.v].emplace_back(e.u, e.w);
                path_length = dijkstra(n, graph, source, destination);
                if (path_length == target) break;
                e.w = -1;
            }
        }
    }

    if (path_length != target) {
        std::cout << "[]\n";
        return;
    }

    for (const auto& e : edges)
        std::cout << "[" << e.u << ", " << e.v << ", " << e.w << "]\n";
}

int main() {
    int n = 4;
    std::vector<GraphEdge> edges = {{1,0,4},{1,2,3},{2,3,5},{0,3,-1}};
    int source = 0;
    int destination = 2;
    int target = 6;
    modifyGraphEdges(n, edges, source, destination, target);
    return 0;
}

JavaScript

// JavaScript solution using Dijkstra and prioritizing -1 edges
class Edge {
    constructor(to, weight) {
        this.to = to;
        this.weight = weight;
    }
}

class GraphEdge {
    constructor(u, v, w) {
        this.u = u;
        this.v = v;
        this.w = w;
    }
}

function dijkstra(n, graph, source) {
    const dist = Array(n).fill(Infinity);
    dist[source] = 0;

    const pq = new MinPriorityQueue({
        compare: (a, b) => a[0] - b[0]
    });
    pq.enqueue([0, source]);

    while (!pq.isEmpty()) {
        const [d, u] = pq.dequeue();

        if (d > dist[u]) continue;

        for (const edge of graph[u]) {
            if (dist[u] + edge.weight < dist[edge.to]) {
                dist[edge.to] = dist[u] + edge.weight;
                pq.enqueue([dist[edge.to], edge.to]);
            }
        }
    }
    return dist;
}

function modifyGraphEdges(n, edgeList, source, destination, target) {
    const edges = edgeList.map(([u, v, w]) => new GraphEdge(u, v, w));
    const graph = Array.from({ length: n }, () => []);

    for (const { u, v, w } of edges) {
        if (w !== -1) {
            graph[u].push(new Edge(v, w));
            graph[v].push(new Edge(u, w));
        }
    }

    let dist = dijkstra(n, graph, source);
    let pathLength = dist[destination];

    if (pathLength === target) {
        for (const edge of edges) {
            if (edge.w === -1) {
                edge.w = 1;
            }
        }
    } else {
        for (const edge of edges) {
            if (edge.w === -1) {
                edge.w = target - pathLength;
                graph[edge.u].push(new Edge(edge.v, edge.w));
                graph[edge.v].push(new Edge(edge.u, edge.w));
                dist = dijkstra(n, graph, source);
                pathLength = dist[destination];
                if (pathLength === target) break;
                edge.w = -1;
            }
        }
    }

    if (pathLength !== target) {
        return [];
    }

    return edges.map(edge => [edge.u, edge.v, edge.w]);
}

// Usage
const n = 4;
const edgeList = [[1,0,4],[1,2,3],[2,3,5],[0,3,-1]];
const source = 0;
const destination = 2;
const target = 6;
console.log(modifyGraphEdges(n, edgeList, source, destination, target));

// C solution using Dijkstra and prioritizing -1 edges
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <stdbool.h>
#include <queue>

#define MAXN 100
#define INF INT_MAX

typedef struct {
    int to, weight;
} Edge;

typedef struct {
    int node, dist;
} DijkstraNode;

typedef struct {
    int u, v, w;
} GraphEdge;

int compare(const void* a, const void* b) {
    return ((DijkstraNode*)a)->dist - ((DijkstraNode*)b)->dist;
}

void dijkstra(int n, int src, Edge graph[][MAXN], int* dist) {
    bool visited[n];
    for (int i = 0; i < n; i++) dist[i] = INF, visited[i] = false;
    dist[src] = 0;
    
    DijkstraNode queue[MAXN * MAXN];
    int queueSize = 0;

    queue[queueSize++] = (DijkstraNode){src, 0};
    qsort(queue, queueSize, sizeof(DijkstraNode), compare);
    
    while (queueSize) {
        DijkstraNode current = queue[--queueSize];
        int u = current.node;

        if (visited[u]) continue;
        visited[u] = true;

        for (int i = 0; i < n; i++) {
            Edge e = graph[u][i];
            if (e.weight == 0) continue;

            int alt = dist[u] + e.weight;
            if (alt < dist[e.to]) {
                dist[e.to] = alt;
                queue[queueSize++] = (DijkstraNode){e.to, alt};
                qsort(queue, queueSize, sizeof(DijkstraNode), compare);
            }
        }
    }
}

void modifyGraphEdges(int n, GraphEdge edges[], int edgesSize, int source, int destination, int target) {
    Edge graph[MAXN][MAXN] = {0};
    for (int i = 0; i < edgesSize; i++) {
        graph[edges[i].u][edges[i].v] = (Edge){edges[i].v, edges[i].w};
        graph[edges[i].v][edges[i].u] = (Edge){edges[i].u, edges[i].w};
    }

    int dist[MAXN];
    dijkstra(n, source, graph, dist);

    for (int i = 0; i < edgesSize; i++) {
        if (edges[i].w == -1) {
            int delta = target - dist[destination];
            if (delta > 0) {
                graph[edges[i].u][edges[i].v].weight = delta;
                graph[edges[i].v][edges[i].u].weight = delta;
                edges[i].w = delta;
                dijkstra(n, source, graph, dist);
                if (dist[destination] == target)
                    break;
            }
        }
    }

    if (dist[destination] != target) {
        printf("[]\n");
        return;
    }

    for (int i = 0; i < edgesSize; i++)
        printf("[%d, %d, %d]\n", edges[i].u, edges[i].v, edges[i].w);
}

int main() {
    int n = 4;
    GraphEdge edges[] = {{1,0,4},{1,2,3},{2,3,5},{0,3,-1}};
    int edgesSize = 4;
    int source = 0;
    int destination = 2;
    int target = 6;
    modifyGraphEdges(n, edges, edgesSize, source, destination, target);
    return 0;
}

// C# solution using Dijkstra and prioritizing -1 edges
using System;
using System.Collections.Generic;

class Edge {
    public int To, Weight;
    public Edge(int to, int weight) {
        To = to;
        Weight = weight;
    }
}

class GraphEdge {
    public int U, V, W;
    public GraphEdge(int u, int v, int w) {
        U = u; V = v; W = w;
    }
}

class GraphModifier {
    public static int Dijkstra(int n, List<List<Edge>> graph, int source, int destination) {
        int[] dist = new int[n];
        Array.Fill(dist, int.MaxValue);
        dist[source] = 0;

        var pq = new SortedSet<(int, int)>(Comparer<(int, int)>.Create((x, y) => x.Item1 == y.Item1 ? x.Item2.CompareTo(y.Item2) : x.Item1.CompareTo(y.Item1)));
        pq.Add((0, source));

        while (pq.Count > 0) {
            var current = pq.Min;
            pq.Remove(current);

            int d = current.Item1, u = current.Item2;
            if (d > dist[u]) continue;

            foreach (var edge in graph[u]) {
                if (dist[u] + edge.Weight < dist[edge.To]) {
                    pq.Remove((dist[edge.To], edge.To));
                    dist[edge.To] = dist[u] + edge.Weight;
                    pq.Add((dist[edge.To], edge.To));
                }
            }
        }
        return dist[destination];
    }

    public static void ModifyGraphEdges(int n, List<GraphEdge> edges, int source, int destination, int target) {
        List<List<Edge>> graph = new List<List<Edge>>(n);
        for (int i = 0; i < n; i++)
            graph.Add(new List<Edge>());

        foreach (var e in edges) {
            if (e.W != -1) {
                graph[e.U].Add(new Edge(e.V, e.W));
                graph[e.V].Add(new Edge(e.U, e.W));
            }
        }

        int pathLength = Dijkstra(n, graph, source, destination);

        if (pathLength == target) {
            foreach (var e in edges) if (e.W == -1) e.W = 1;
        } else {
            foreach (var e in edges) {
                if (e.W == -1) {
                    e.W = target - pathLength;
                    graph[e.U].Add(new Edge(e.V, e.W));
                    graph[e.V].Add(new Edge(e.U, e.W));
                    pathLength = Dijkstra(n, graph, source, destination);
                    if (pathLength == target) break;
                    e.W = -1;
                }
            }
        }

        if (pathLength != target) {
            Console.WriteLine("[]");
            return;
        }

        foreach (var e in edges)
            Console.WriteLine($"[{e.U}, {e.V}, {e.W}]");
    }

    public static void Main() {
        int n = 4;
        List<GraphEdge> edges = new List<GraphEdge> { new GraphEdge(1,0,4), new GraphEdge(1,2,3), new GraphEdge(2,3,5), new GraphEdge(0,3,-1) };
        int source = 0;
        int destination = 2;
        int target = 6;
        ModifyGraphEdges(n, edges, source, destination, target);
    }
}

The Python version prioritizes initial, valid path edges with re-examinations using Dijkstra's algorithm to verify once modifications to -1 edge values reflect the target clause. Employs tuple-priority queue stands for efficient shortest path tracking during each stage.

Complexity

Time Complexity: O(E log V), using heapq priority queues for Dijkstra processing efficiency.
Space Complexity: O(V+E), consistent with standard Dijkstra methodologies.

Try this approach in the editor

Approach 5: Shortest Path (Dijkstra's Algorithm)

First, we ignore the edges with a weight of -1 and use Dijkstra's algorithm to find the shortest distance d from source to destination.

If d < target, it means there is a shortest path composed entirely of positive weight edges. No matter how we modify the edges with a weight of -1, we cannot make the shortest distance from source to destination equal to target. Therefore, there is no modification scheme that satisfies the problem, and we can return an empty array.
If d = target, it means there is a shortest path composed entirely of positive weight edges, and its length is target. In this case, we can modify all edges with a weight of -1 to the maximum value 2 times 10^9.
If d > target, we can try to add an edge with a weight of -1 to the graph, set the weight of the edge to 1, and then use Dijkstra's algorithm again to find the shortest distance d from source to destination.
- If the shortest distance d leq target, it means that after adding this edge, the shortest path can be shortened, and the shortest path must pass through this edge. Then we only need to change the weight of this edge to target-d+1 to make the shortest path equal to target. Then we can modify the remaining edges with a weight of -1 to the maximum value 2 times 10^9.
- If the shortest distance d > target, it means that after adding this edge, the shortest path will not be shortened. Then we greedily keep the weight of this edge as -1 and continue to try to add the remaining edges with a weight of -1.

The time complexity is O(n^3), and the space complexity is O(n^2), where n is the number of points in the graph.

TypeScript

function modifiedGraphEdges(
    n: number,
    edges: number[][],
    source: number,
    destination: number,
    target: number,
): number[][] {
    const inf = 2e9;
    const dijkstra = (edges: number[][]): number => {
        const g: number[][] = Array(n)
            .fill(0)
            .map(() => Array(n).fill(inf));
        const dist: number[] = Array(n).fill(inf);
        const vis: boolean[] = Array(n).fill(false);
        for (const [a, b, w] of edges) {
            if (w === -1) {
                continue;
            }
            g[a][b] = w;
            g[b][a] = w;
        }
        dist[source] = 0;
        for (let i = 0; i < n; ++i) {
            let k = -1;
            for (let j = 0; j < n; ++j) {
                if (!vis[j] && (k === -1 || dist[j] < dist[k])) {
                    k = j;
                }
            }
            vis[k] = true;
            for (let j = 0; j < n; ++j) {
                dist[j] = Math.min(dist[j], dist[k] + g[k][j]);
            }
        }
        return dist[destination];
    };
    let d = dijkstra(edges);
    if (d < target) {
        return [];
    }
    let ok = d === target;
    for (const e of 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 ok ? edges : [];
}

func modifiedGraphEdges(n int, edges [][]int, source int, destination int, target int) [][]int {
	const inf int = 2e9
	dijkstra := func(edges [][]int) int {
		g := make([][]int, n)
		dist := make([]int, n)
		vis := make([]bool, n)
		for i := range g {
			g[i] = make([]int, n)
			for j := range g[i] {
				g[i][j] = inf
			}
			dist[i] = inf
		}
		dist[source] = 0
		for _, e := range edges {
			a, b, w := e[0], e[1], e[2]
			if w == -1 {
				continue
			}
			g[a][b], g[b][a] = w, w
		}
		for i := 0; i < n; i++ {
			k := -1
			for j := 0; j < n; j++ {
				if !vis[j] && (k == -1 || dist[j] < dist[k]) {
					k = j
				}
			}
			vis[k] = true
			for j := 0; j < n; j++ {
				dist[j] = min(dist[j], dist[k]+g[k][j])
			}
		}
		return dist[destination]
	}
	d := dijkstra(edges)
	if d < target {
		return [][]int{}
	}
	ok := d == target
	for _, e := range 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
		}
	}
	if ok {
		return edges
	}
	return [][]int{}
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Approach 1: Dijkstra's Algorithm with Binary Search	Time Complexity: O(E * log(V) * log(W)), where E is the number of edges, V is the number of vertices, and W is the weight range (binary search range). Space Complexity: O(V + E), mainly for storing the graph structure and distances.
Approach 2: Iterative Adjustment with BFS	Time Complexity: O(E * V * log(W)), where E is the number of edges, V is the number of vertices, and W is the binary search range for weights. Space Complexity: O(V + E) for the graph representation and distance tracking.
Binary Search on Edge Weights	Time Complexity: O(VE), for Bellman-Ford's method dynamics integrated into the binary search. Space Complexity: O(V), storing initial distances as necessary.
Dijkstra with Prioritization for -1 Edges	Time Complexity: O(E log V), using heapq priority queues for Dijkstra processing efficiency. Space Complexity: O(V+E), consistent with standard Dijkstra methodologies.
Shortest Path (Dijkstra's Algorithm)	–

Complexity analysis

Approach	Time	Space	When to Use
Dijkstra with Prioritization for -1 Edges	O(m log n)	O(n + m)	Best general solution when graph is large and multiple unknown edges exist
Binary Search on Edge Weights + Dijkstra	O(k * m log n)	O(n + m)	Useful when searching the correct value for a specific adjustable edge
Dijkstra with Binary Search Strategy	O(k * m log n)	O(n + m)	When baseline shortest path must be measured before enabling -1 edges
Iterative Adjustment with BFS	O(k * (n + m))	O(n + m)	Simpler implementation when graph size is moderate and weights are adjusted gradually

Frequently asked questions

Is Modify Graph Edge Weights easy or hard?

Modify Graph Edge Weights is classified as a Hard problem. It combines shortest path algorithms with dynamic weight assignment, requiring careful reasoning about how edge adjustments affect the final path distance.

How to solve Modify Graph Edge Weights in O(m log n)?

Run Dijkstra's shortest path while treating -1 edges as adjustable. Start with minimal weights and track how far the shortest path is from the target. When the path is shorter than required, increase the weight of one of the adjustable edges along that path so the total distance becomes exactly the target.

What is the best approach for Modify Graph Edge Weights?

The most efficient approach uses Dijkstra's algorithm while dynamically assigning values to edges with weight -1. A priority queue processes nodes by shortest distance, and adjustable edges are tuned so the final path length equals the target. This keeps the complexity around O(m log n) and works well for large graphs.

What data structure is used in Modify Graph Edge Weights?

The core data structure is a min-heap priority queue used inside Dijkstra's algorithm. The graph is typically stored as an adjacency list for efficient traversal. These structures allow efficient shortest-path updates while exploring nodes.

What is the time complexity of Modify Graph Edge Weights?

The optimal Dijkstra-based solution runs in O(m log n) time and O(n + m) space, where n is the number of nodes and m is the number of edges. Approaches that repeatedly run Dijkstra during binary search can increase complexity to O(k * m log n), where k is the number of adjustable edges.

Is Modify Graph Edge Weights asked at Google, Amazon, or Meta?

Graph shortest path problems with dynamic edge constraints frequently appear in interviews at companies like Google, Amazon, and Meta. Variants of this question test knowledge of Dijkstra's algorithm, priority queues, and reasoning about weighted graphs.

Is there a Python or Java solution for Modify Graph Edge Weights?

Python and Java implementations typically use adjacency lists and a priority queue for Dijkstra's algorithm. Python uses the heapq module, while Java uses PriorityQueue. Both implementations maintain distance arrays and update adjustable edges during path computation.

Modify Graph Edge Weights solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Dijkstra's Algorithm with Binary Search

Approach 2: Approach 2: Iterative Adjustment with BFS

Approach 3: Binary Search on Edge Weights

Approach 4: Dijkstra with Prioritization for -1 Edges

Approach 5: Shortest Path (Dijkstra's Algorithm)

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Modify Graph Edge Weights solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Dijkstra's Algorithm with Binary Search

Approach 2: Approach 2: Iterative Adjustment with BFS

Approach 3: Binary Search on Edge Weights

Approach 4: Dijkstra with Prioritization for -1 Edges

Approach 5: Shortest Path (Dijkstra's Algorithm)

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems