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

Minimize the Maximum Edge Weight of Graph

Difficulty: Medium

Problem Description

You are given two integers, n and threshold, as well as a directed weighted graph of n nodes numbered from 0 to n - 1. The graph is represented by a 2D integer array edges, where edges[i] = [Ai, Bi, Wi] indicates that there is an edge going from node Ai to node Bi with weight Wi.

You have to remove some edges from this graph (possibly none), so that it satisfies the following conditions:

  • Node 0 must be reachable from all other nodes.
  • The maximum edge weight in the resulting graph is minimized.
  • Each node has at most threshold outgoing edges.

Return the minimum possible value of the maximum edge weight after removing the necessary edges. If it is impossible for all conditions to be satisfied, return -1.

Key Insights

  • The goal is to ensure all nodes can reach node 0 while minimizing the maximum edge weight in the remaining graph.
  • We can use binary search to find the minimum maximum edge weight that still allows for a valid graph configuration.
  • A graph traversal technique (like BFS or DFS) can verify if the current configuration of edges meets the conditions.

Space and Time Complexity

Time Complexity: O(E log W), where E is the number of edges and W is the range of edge weights. Space Complexity: O(E + V), where E is the number of edges and V is the number of vertices, for the graph representation and traversal.

Solution

The solution employs a binary search on the edge weights. The algorithm works as follows:

  1. Binary Search Setup: Determine the range of possible edge weights (from 1 to the maximum weight in the edges).
  2. Graph Filtering: For each midpoint in the binary search, filter the edges to only include those with weights less than or equal to the midpoint.
  3. Graph Validation: Use BFS or DFS to check if node 0 is reachable from all other nodes under the constraint that no node has more than the allowed threshold of outgoing edges.
  4. Adjust Search Bounds: If all nodes can reach node 0, try to minimize the maximum weight further (search left); otherwise, increase the weight (search right).
  5. Final Result: The smallest weight for which the conditions hold is returned, or -1 if no valid configuration exists.

Code Solutions

def canReachAllNodes(n, edges, maxWeight, threshold):
    from collections import defaultdict, deque
    
    graph = defaultdict(list)
    out_degree = [0] * n
    
    for u, v, w in edges:
        if w <= maxWeight and out_degree[u] < threshold:
            graph[v].append(u)  # reverse the graph for reachability check
            out_degree[u] += 1
            
    reachable = [False] * n
    queue = deque([0])
    reachable[0] = True
    
    while queue:
        node = queue.popleft()
        for neighbor in graph[node]:
            if not reachable[neighbor]:
                reachable[neighbor] = True
                queue.append(neighbor)
    
    return all(reachable)

def minimizeMaxEdgeWeight(n, edges, threshold):
    left, right = 1, max(weight for _, _, weight in edges)
    result = -1
    
    while left <= right:
        mid = (left + right) // 2
        if canReachAllNodes(n, edges, mid, threshold):
            result = mid
            right = mid - 1
        else:
            left = mid + 1
            
    return result

# Example usage
n = 5
edges = [[1,0,1],[2,0,2],[3,0,1],[4,3,1],[2,1,1]]
threshold = 2
print(minimizeMaxEdgeWeight(n, edges, threshold))  # Output: 1
← Back to All Questions