Minimum Weighted Subgraph With the Required Paths Interview Question for Google

Minimum Weight Subgraph Problem

This problem asks us to find the minimum weight subgraph that allows reaching a destination node from two source nodes in a weighted directed graph. If no such subgraph exists, we should return -1.

1. Brute Force Solution

A brute-force approach would involve generating all possible subgraphs and checking if each subgraph satisfies the given conditions (reachability from both sources to the destination). We can implement a depth-first search (DFS) or breadth-first search (BFS) to check for reachability. However, this approach has exponential time complexity, making it impractical for larger graphs.

2. Optimal Solution: Dijkstra's Algorithm

A more efficient approach involves using Dijkstra's algorithm to find the shortest paths from each source node to the destination and from the destination to each source node in the reversed graph. We can then iterate through all nodes and calculate the combined weight of the paths from src1 to the node, src2 to the node, and the node to dest. The minimum of these combined weights will be the answer.

Here's a breakdown of the steps:

Calculate shortest paths from src1 to all nodes: Use Dijkstra's algorithm to find the shortest distance from src1 to every other node in the graph. Store these distances in an array dist1.
Calculate shortest paths from src2 to all nodes: Similarly, use Dijkstra's algorithm to find the shortest distance from src2 to every other node in the graph. Store these distances in an array dist2.
Calculate shortest paths from all nodes to dest: Create a reversed graph by reversing the direction of all edges. Use Dijkstra's algorithm on the reversed graph to find the shortest distance from every node to dest. Store these distances in an array dist_dest.
Iterate through all nodes and find the minimum weight: For each node i, calculate the sum dist1[i] + dist2[i] + dist_dest[i]. Keep track of the minimum of these sums. If any of the distances are infinity (meaning there is no path), skip that node.
Handle no path scenarios: If the minimum weight remains infinity after iterating through all nodes, it means there is no subgraph satisfying the conditions. Return -1.

import heapq
import math

def minimum_weight_subgraph(n, edges, src1, src2, dest):
    def dijkstra(graph, start):
        distances = {node: float('inf') for node in range(n)}
        distances[start] = 0
        pq = [(0, start)]

        while pq:
            dist, u = heapq.heappop(pq)

            if dist > distances[u]:
                continue

            for v, weight in graph.get(u, []):
                if distances[u] + weight < distances[v]:
                    distances[v] = distances[u] + weight
                    heapq.heappush(pq, (distances[v], v))

        return distances

    # Build the graph
    graph = {}
    reversed_graph = {}
    for u, v, weight in edges:
        graph.setdefault(u, []).append((v, weight))
        reversed_graph.setdefault(v, []).append((u, weight))

    # Calculate distances from src1 and src2
    dist1 = dijkstra(graph, src1)
    dist2 = dijkstra(graph, src2)

    # Calculate distances to dest in the reversed graph
    dist_dest = dijkstra(reversed_graph, dest)

    min_weight = float('inf')

    for i in range(n):
        if dist1[i] != float('inf') and dist2[i] != float('inf') and dist_dest[i] != float('inf'):
            min_weight = min(min_weight, dist1[i] + dist2[i] + dist_dest[i])

    return min_weight if min_weight != float('inf') else -1


# 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

result = minimum_weight_subgraph(n, edges, src1, src2, dest)
print(f"Minimum weight subgraph: {result}")  # Output: 9

n = 3
edges = [[0, 1, 1], [2, 1, 1]]
src1 = 0
src2 = 1
dest = 2

result = minimum_weight_subgraph(n, edges, src1, src2, dest)
print(f"Minimum weight subgraph: {result}")  # Output: -1

3. Big O Time Complexity Analysis

Dijkstra's Algorithm: Dijkstra's algorithm, when implemented with a priority queue (heap), has a time complexity of O(E log V), where E is the number of edges and V is the number of vertices (nodes).
Overall Complexity: We run Dijkstra's algorithm three times (from src1, src2, and dest in the reversed graph). Therefore, the overall time complexity is O(3 * E log V), which simplifies to O(E log V).

4. Big O Space Complexity Analysis

Dijkstra's Algorithm: Dijkstra's algorithm uses a distance array of size V to store the shortest distances from the source node to all other nodes. It also uses a priority queue, which, in the worst case, can hold all the nodes in the graph.
Overall Complexity: We store three distance arrays (dist1, dist2, dist_dest), each of size V. We also store the graph and reversed graph, which take O(E) space. Thus, the overall space complexity is O(3V + E), which simplifies to O(V + E).

5. Edge Cases and Handling

Disconnected Graph: If there is no path from src1 or src2 to dest, the Dijkstra's algorithm will result in float('inf') distances. The code handles this case by checking for float('inf') distances and returning -1 if the minimum weight remains float('inf') after iterating through all nodes.
Negative Edge Weights: Dijkstra's algorithm does not work correctly with negative edge weights. If the graph contains negative edge weights, we would need to use the Bellman-Ford algorithm instead, which has a time complexity of O(V * E).
Zero Weight Edges: The algorithm handles zero weight edges correctly. They do not cause any issues.
Large Graphs: For extremely large graphs, consider using more advanced graph processing techniques or distributed computing to improve performance.