LeetCode Solutions Blog

Minimum Weighted Subgraph With the Required Paths

Number: 2321

Difficulty: Hard

Paid? No

Companies: Google

Problem Description

Given a weighted directed graph with n nodes numbered from 0 to n-1 and a list of directed edges with their weights, find a subgraph (a subset of the original edges) that allows both src1 and src2 to reach dest. The objective is to minimize the sum of weights of the selected edges. If no such subgraph exists, return -1.

Key Insights

The problem essentially requires two paths: one from src1 to dest and one from src2 to dest.
Instead of independently finding two paths, we can leverage the observation that there exists an intermediate node v such that:
- There is a shortest path from src1 to v.
- There is a shortest path from src2 to v.
- And there is a shortest path from v to dest.
By reversing the graph, the path from any node v to dest in the original graph becomes a path from dest to v in the reversed graph.
Running three instances of Dijkstra's algorithm (from src1, from src2, and from dest on the reversed graph) gives the minimum distance from the respective source nodes to every other node.
The answer is the minimum over all nodes v of (dist(src1, v) + dist(src2, v) + dist(v, dest)). If any part is unreachable for a given v, skip that candidate.

Space and Time Complexity

Time Complexity: O(E log N), where E is the number of edges and N is the number of nodes because Dijkstra's algorithm is run three times. Space Complexity: O(N + E) for the graph representation and distance arrays.

Solution

To solve the problem, we use Dijkstra's algorithm three times:

From src1 on the original graph to get distances from src1 to every node.
From src2 on the original graph to get distances from src2 to every node.
From dest on the reversed graph to get distances from every node to dest. For each node v, we calculate totalCost = dist1[v] + dist2[v] + dist3[v] (where dist3[v] is the distance from v to dest calculated on the reversed graph). The answer is the minimum totalCost among all nodes v that are reachable from the respective sources. If no such candidate exists, we return -1.

Code Solutions

import heapq

def minimumWeight(n, edges, src1, src2, dest):
    # Build graph in normal direction and reversed direction
    graph = [[] for _ in range(n)]
    reverse_graph = [[] for _ in range(n)]
    
    # Build both graphs according to the given directed weighted edges
    for u, v, w in edges:
        graph[u].append((v, w))
        reverse_graph[v].append((u, w))
    
    # Function to perform Dijkstra's algorithm from a source node
    def dijkstra(start, graph):
        dist = [float('inf')] * n
        dist[start] = 0
        minheap = [(0, start)]  # (distance, node)
        while minheap:
            d, node = heapq.heappop(minheap)
            # If we have already found a better path, skip this entry
            if d > dist[node]:
                continue
            # Relax edges out of current node
            for neighbor, weight in graph[node]:
                new_d = d + weight
                if new_d < dist[neighbor]:
                    dist[neighbor] = new_d
                    heapq.heappush(minheap, (new_d, neighbor))
        return dist

    # Compute distances from src1 and src2 on the original graph.
    dist_from_src1 = dijkstra(src1, graph)
    dist_from_src2 = dijkstra(src2, graph)
    
    # Compute distances from dest on the reversed graph (equivalent to distances from every node to dest)
    dist_to_dest = dijkstra(dest, reverse_graph)
    
    # Compute the minimum combined weight
    result = float('inf')
    for node in range(n):
        total = dist_from_src1[node] + dist_from_src2[node] + dist_to_dest[node]
        if total < result:
            result = total
            
    # If result remains infinity, then there's no valid subgraph meeting requirements.
    return -1 if result == float('inf') else result

# Example usage:
# n = 6, edges = [[0,2,2],[0,5,6],[1,0,3],[1,4,5],[2,1,1],[2,3,3],[2,3,4],[3,4,2],[4,5,1]], src1 = 0, src2 = 1, dest = 5
# Expected output: 9
print(minimumWeight(6, [[0,2,2],[0,5,6],[1,0,3],[1,4,5],[2,1,1],[2,3,3],[2,3,4],[3,4,2],[4,5,1]], 0, 1, 5))