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

Minimum Weighted Subgraph With the Required Paths

Difficulty: Hard

Problem Description

You are given an integer n denoting the number of nodes of a weighted directed graph. The nodes are numbered from 0 to n - 1. You are also given a 2D integer array edges where edges[i] = [from_i, to_i, weight_i] denotes that there exists a directed edge from from_i to to_i with weight weight_i. Lastly, you are given three distinct integers src1, src2, and dest denoting three distinct nodes of the graph. Return the minimum weight of a subgraph of the graph such that it is possible to reach dest from both src1 and src2 via a set of edges of this subgraph. In case such a subgraph does not exist, return -1.

Key Insights

  • The problem requires finding a weighted subgraph that connects two source nodes to a destination node.
  • To achieve this, we need to identify paths from src1 and src2 to dest.
  • The solution involves determining which edges are necessary to form valid paths while minimizing the total weight of the subgraph.
  • We can represent the graph using adjacency lists and utilize Dijkstra's algorithm to find the shortest paths from each source to the destination.
  • The problem is hard due to the need to manage multiple paths and ensure they share edges for minimal weight.

Space and Time Complexity

Time Complexity: O(E log V) where E is the number of edges and V is the number of vertices, due to the Dijkstra's algorithm.
Space Complexity: O(V + E) for storing the graph representation and the priority queue.

Solution

To solve the problem, we will use Dijkstra's algorithm to find the shortest path from both src1 and src2 to dest. We need to keep track of the edges used to reach the destination and their corresponding weights. After calculating the shortest paths, we will analyze the edges to determine the minimum total weight of the subgraph that connects both src1 and src2 to dest.

  1. Construct the graph using an adjacency list.
  2. Use Dijkstra’s algorithm to find the shortest path from src1 and src2 to dest, storing the paths and their weights.
  3. Identify edges that are common in both paths and calculate the minimum weight required to connect src1 and src2 to dest.
  4. Return the minimum weight (or -1 if no valid subgraph exists).

Code Solutions

import heapq
from collections import defaultdict

def minimumWeight(n, edges, src1, src2, dest):
    graph = defaultdict(list)
    for u, v, w in edges:
        graph[u].append((v, w))
    
    def dijkstra(source):
        dist = [float('inf')] * n
        dist[source] = 0
        pq = [(0, source)]  # (weight, node)
        while pq:
            curr_weight, u = heapq.heappop(pq)
            if curr_weight > dist[u]:
                continue
            for v, weight in graph[u]:
                if curr_weight + weight < dist[v]:
                    dist[v] = curr_weight + weight
                    heapq.heappush(pq, (dist[v], v))
        return dist
    
    dist_from_src1 = dijkstra(src1)
    dist_from_src2 = dijkstra(src2)
    dist_from_dest = dijkstra(dest)
    
    min_weight = float('inf')
    
    for u in range(n):
        if dist_from_src1[u] < float('inf') and dist_from_src2[u] < float('inf') and dist_from_dest[u] < float('inf'):
            total_weight = dist_from_src1[u] + dist_from_src2[u] + dist_from_dest[u]
            min_weight = min(min_weight, total_weight)
    
    return min_weight if min_weight < float('inf') else -1
← Back to All Questions