LeetCode Solutions Blog

Modify Graph Edge Weights

Number: 2803

Difficulty: Hard

Paid? No

Companies: Google

Problem Description

Given an undirected, weighted, and connected graph with n nodes and a list of edges (some with unknown weight, i.e. -1), assign a positive integer (in [1, 2 * 10^9]) to every edge whose weight is -1 so that the shortest distance between a specified source and destination becomes exactly target. You are not allowed to change edges that already have a positive weight. If one such modification is possible, return an array of all edges with the modified weights (order may change); otherwise, return an empty array.

Key Insights

First, use Dijkstra’s algorithm twice:
- Once setting all unknown (-1) weights to 1 to get the minimum possible distance.
- Once setting all unknown weights to a very large number (2*10^9) to get the maximum possible distance.
If the target is not between these two computed distances, a solution is impossible.
Compute a helper array (distances from each node to the destination) using Dijkstra’s reversed graph where unknown weights are 1. This will be used to “reserve” the necessary slack for adjustment.
Do a “forward” Dijkstra from the source. When relaxing an edge with unknown weight, determine the required weight = target - (current distance from source) - (precomputed distance from neighbor to destination). This adjustment “forces” the shortest path to add up to target.
Finally, assign 1 to any remaining unknown edges that were not used (or didn’t require adjustment) and return all edges.

Space and Time Complexity

Time Complexity: O(m log n) where m is the number of edges and n is the number of nodes (Dijkstra’s algorithm is run multiple times). Space Complexity: O(n + m) for storing the graph and auxiliary arrays.

Solution

We first run Dijkstra’s algorithm from the destination in the reverse graph with all unknown edges set to a weight of 1. This gives us, for every node, the minimum distance to the destination ignoring modifications. Then, we run a forward Dijkstra from the source. For each edge which originally had weight -1, we calculate the would–be needed weight that makes current_distance + (new_weight) + (distance from neighbor to destination) exactly equal to target. If the computed weight is below 1, we use 1; if above 210^9, we use 210^9. This update “fixes” that unknown edge when it is used in the shortest path so that the overall distance is forced to target. Finally, we verify that the distance from source to destination in our modified graph is exactly target. If so, we update all remaining -1 edges to 1 and output the modified edge list; if not, we return an empty array.

Key data structures:

An adjacency list (graph) representation.
A min heap (priority queue) for Dijkstra.
Two distance arrays (one from the destination; one from the source with modifications).

The “gotcha” is ensuring that the computed new weight for an edge exactly “absorbs” the slack needed to reach the target distance while also keeping the modification valid (in [1, 2*10^9]).

Code Solutions

import heapq
from collections import defaultdict
from math import inf

def modifiedGraphEdges(n, edges, source, destination, target):
    # Build graph and reverse graph while recording edge indices.
    graph = defaultdict(list)
    rev_graph = defaultdict(list)
    for i, (u, v, w) in enumerate(edges):
        graph[u].append((v, w, i))
        graph[v].append((u, w, i))
        rev_graph[u].append((v, w))
        rev_graph[v].append((u, w))
        
    # Helper function: Dijkstra's algorithm returning distances.
    def dijkstra(start, graph_dict, assign_for_unknown):
        dist = [inf] * n
        dist[start] = 0
        heap = [(0, start)]
        while heap:
            d, node = heapq.heappop(heap)
            if d != dist[node]:
                continue
            for nbr, w, *rest in graph_dict[node]:
                weight = w if w != -1 else assign_for_unknown
                nd = d + weight
                if nd < dist[nbr]:
                    dist[nbr] = nd
                    heapq.heappush(heap, (nd, nbr))
        return dist

    # Precompute distances from every node to destination (reverse Dijkstra)
    # with unknown edges treated as weight = 1.
    # Since graph is undirected, we can just run from destination.
    rev_dist = [inf] * n
    rev_dist[destination] = 0
    heap = [(0, destination)]
    while heap:
        d, node = heapq.heappop(heap)
        if d != rev_dist[node]:
            continue
        for nbr, w, in graph[node]:
            weight = w if w != -1 else 1
            nd = d + weight
            if nd < rev_dist[nbr]:
                rev_dist[nbr] = nd
                heapq.heappush(heap, (nd, nbr))
    
    # Run forward Dijkstra from source using modified weights when needed.
    dist = [inf] * n
    dist[source] = 0
    heap = [(0, source)]
    # We copy the edge list so that we can modify unknown weights
    newEdges = edges[:]
    while heap:
        d, node = heapq.heappop(heap)
        if d != dist[node]:
            continue
        # If we reached destination, no need to continue processing.
        for nbr, w, idx in graph[node]:
            # If edge is fixed, its weight stays unchanged.
            if w != -1:
                nd = d + w
                if nd < dist[nbr]:
                    dist[nbr] = nd
                    heapq.heappush(heap, (nd, nbr))
            else:
                # For unknown weight edge, determine the weight needed so that:
                # d + newWeight + rev_dist[nbr] == target.
                # If rev_dist[nbr] == inf, then nbr is not reachable properly.
                required = target - d - rev_dist[nbr]
                if required < 1:
                    required = 1
                if required > 2 * 10**9:
                    required = 2 * 10**9
                # Use computed weight.
                nd = d + required
                if nd < dist[nbr]:
                    dist[nbr] = nd
                    heapq.heappush(heap, (nd, nbr))
                    newEdges[idx][2] = required  # update edge weight in our answer
                    # Update the graph with the new fixed weight.
                    # Because the graph is undirected, update the paired edge as well.
                    for i, (nbr2, w2, idx2) in enumerate(graph[nbr]):
                        if nbr2 == node and idx2 == idx:
                            graph[nbr][i] = (node, required, idx2)
                            break

    # After the forward pass, if distance[target] != target, then no solution.
    if dist[destination] != target:
        return []
    # For any remaining edge with weight -1, set weight to 1.
    for i, edge in enumerate(newEdges):
        if edge[2] == -1:
            newEdges[i][2] = 1
    return newEdges

# Example usage:
if __name__ == "__main__":
    n = 5
    edges = [[4,1,-1],[2,0,-1],[0,3,-1],[4,3,-1]]
    source = 0
    destination = 1
    target = 5
    print(modifiedGraphEdges(n, edges, source, destination, target))