We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Modify Graph Edge Weights

Difficulty: Hard

Problem Description

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, while others have a positive weight. Your task is to modify all edges with a weight of -1 by assigning them positive integer values in the range [1, 2 * 10^9] so that the shortest distance between the nodes source and destination becomes equal to an integer target. 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.

Key Insights

  • The graph is undirected and connected, ensuring that a path exists between any two nodes.
  • We can only modify edges with a weight of -1, and we need to ensure that the total weight between source and destination equals the target.
  • The task requires careful assignment of weights to the edges with -1 to achieve the target distance.
  • A shortest path algorithm (like Dijkstra's or Bellman-Ford) can help calculate the current distances and determine how to adjust the weights of -1 edges.

Space and Time Complexity

Time Complexity: O(E + V log V) where E is the number of edges and V is the number of vertices (depending on the shortest path algorithm used). Space Complexity: O(V + E) for storing graph structures and distances.

Solution

To solve this problem, we can use the following approach:

  1. Construct the graph from the edges.
  2. Use a shortest path algorithm (like Dijkstra's) to calculate the shortest path from the source to the destination while ignoring edges with a weight of -1.
  3. Determine the current shortest path distance and identify the edges with -1 that can be adjusted.
  4. Calculate the required weights for the -1 edges to achieve the target distance.
  5. If it's possible to assign weights to the -1 edges to reach the target, return the modified edges; otherwise, return an empty array.

Code Solutions

import heapq

def modifyGraphEdgeWeights(n, edges, source, destination, target):
    graph = {i: [] for i in range(n)}
    for a, b, w in edges:
        graph[a].append((b, w))
        graph[b].append((a, w))

    def dijkstra(src):
        dist = [float('inf')] * n
        dist[src] = 0
        pq = [(0, src)]
        while pq:
            curr_dist, node = heapq.heappop(pq)
            if curr_dist > dist[node]:
                continue
            for neighbor, weight in graph[node]:
                if weight != -1:  # Only consider positive weights
                    new_dist = curr_dist + weight
                    if new_dist < dist[neighbor]:
                        dist[neighbor] = new_dist
                        heapq.heappush(pq, (new_dist, neighbor))
        return dist

    current_dist = dijkstra(source)
    
    if current_dist[destination] > target:
        return []  # Impossible to reach target
    
    missing_distance = target - current_dist[destination]
    edges_with_neg1 = [(a, b) for a, b, w in edges if w == -1]
    
    for (a, b) in edges_with_neg1:
        if missing_distance <= 0:
            break
        # Assign the minimum weight possible to reach the target
        weight_to_assign = min(missing_distance, 2 * 10**9)
        graph[a].append((b, weight_to_assign))
        graph[b].append((a, weight_to_assign))
        missing_distance -= weight_to_assign

    if missing_distance > 0:
        return []
    
    # Prepare the output
    result = []
    for a, b, w in edges:
        if w == -1:
            # Find the modified weight
            modified_weight = min(weight_to_assign, 2 * 10**9)
            result.append([a, b, modified_weight])
        else:
            result.append([a, b, w])
    
    return result
← Back to All Questions