2203. Minimum Weighted Subgraph With the Required Paths

Problem Description

You have a weighted directed graph with n nodes numbered from 0 to n - 1. The graph is defined by an array edges where each element edges[i] = [from_i, to_i, weight_i] represents a directed edge from node from_i to node to_i with weight weight_i.

You are given three distinct nodes: src1, src2, and dest.

Your task is to find the minimum total weight of a subgraph that allows both src1 and src2 to reach dest. A subgraph is formed by selecting some edges from the original graph, and its weight is the sum of all selected edges' weights.

The key requirement is that there must exist paths:

From src1 to dest using only edges in the subgraph
From src2 to dest using only edges in the subgraph

Return the minimum weight of such a subgraph. If no such subgraph exists (meaning it's impossible for both source nodes to reach the destination), return -1.

Example scenario: Imagine you have two starting points and one destination. You want to find the cheapest way to build roads such that both starting points can reach the destination. The roads can be shared - if both paths use the same road, you only count its weight once in the total.

The solution uses Dijkstra's algorithm three times:

From src1 to all nodes (forward graph)
From src2 to all nodes (forward graph)
From dest to all nodes (reverse graph)

For each potential intermediate node i, it calculates the total weight as: distance(src1 → i) + distance(src2 → i) + distance(i → dest). The minimum among all such sums is the answer.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

The key insight is that when both src1 and src2 need to reach dest, their paths will likely merge at some intermediate node before continuing to the destination. Think of it like two rivers flowing toward the ocean - they might join at some point and then flow together.

Let's call this meeting point node i. The optimal subgraph would consist of:

The shortest path from src1 to i
The shortest path from src2 to i
The shortest path from i to dest

These three path segments together form our subgraph, and their total weight is what we want to minimize.

But which node should be the meeting point? We don't know in advance, so we need to try all possible nodes as potential meeting points and find the one that gives us the minimum total weight.

For any candidate meeting point i, the total weight would be: distance(src1 → i) + distance(src2 → i) + distance(i → dest)

To efficiently calculate these distances:

We run Dijkstra from src1 to get shortest distances from src1 to all nodes
We run Dijkstra from src2 to get shortest distances from src2 to all nodes
For the third part, we need distances from each node to dest. Instead of running Dijkstra from every node to dest, we can be clever: we reverse all edges in the graph and run Dijkstra from dest. This gives us the shortest distances from all nodes to dest in the original graph.

After getting these three distance arrays (d1, d2, d3), for each node i, we calculate d1[i] + d2[i] + d3[i]. The minimum value among all nodes is our answer.

If the minimum value is infinity (meaning at least one of the required paths doesn't exist), we return -1.

Learn more about Graph and Shortest Path patterns.

Solution Approach

The implementation uses Dijkstra's algorithm as the core component to find shortest paths. Here's how the solution works step by step:

1. Graph Construction:

g = defaultdict(list)   # Original graph
rg = defaultdict(list)  # Reverse graph
for f, t, w in edges:
    g[f].append((t, w))
    rg[t].append((f, w))

We build two adjacency lists:

g: The original directed graph where g[u] contains all nodes v reachable from u with their edge weights
rg: The reverse graph where all edges are flipped. This is crucial for finding distances from all nodes to dest

2. Dijkstra's Algorithm Implementation:

def dijkstra(g, u):
    dist = [inf] * n
    dist[u] = 0
    q = [(0, u)]
    while q:
        d, u = heappop(q)
        if d > dist[u]:
            continue
        for v, w in g[u]:
            if dist[v] > dist[u] + w:
                dist[v] = dist[u] + w
                heappush(q, (dist[v], v))
    return dist

The algorithm uses a min-heap priority queue to always process the node with minimum distance first. It returns an array where dist[i] represents the shortest distance from source u to node i.

3. Computing Three Distance Arrays:

d1 = dijkstra(g, src1)   # Distances from src1 to all nodes
d2 = dijkstra(g, src2)   # Distances from src2 to all nodes
d3 = dijkstra(rg, dest)  # Distances from all nodes to dest

d1[i]: shortest distance from src1 to node i
d2[i]: shortest distance from src2 to node i
d3[i]: shortest distance from node i to dest (computed using the reverse graph)

4. Finding the Minimum Weight:

ans = min(sum(v) for v in zip(d1, d2, d3))
return -1 if ans >= inf else ans

For each node i from 0 to n-1, we calculate the total weight if i is the meeting point: d1[i] + d2[i] + d3[i].

The zip(d1, d2, d3) creates tuples (d1[i], d2[i], d3[i]) for each index i. We sum each tuple and find the minimum.

If the minimum is still infinity (meaning no valid path exists), we return -1.

Time Complexity: O(E log V) for each Dijkstra run, where E is the number of edges and V is the number of vertices. Since we run Dijkstra three times, the total is O(3 * E log V) = O(E log V).

Space Complexity: O(V + E) for storing the graphs and distance arrays.

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Consider a graph with 4 nodes (0, 1, 2, 3) and the following edges:

Edge 0→1 with weight 2
Edge 0→2 with weight 5
Edge 1→2 with weight 1
Edge 1→3 with weight 3
Edge 2→3 with weight 1

Let src1 = 0, src2 = 1, and dest = 3.

Step 1: Build the graphs

Original graph g:
- 0: [(1,2), (2,5)]
- 1: [(2,1), (3,3)]
- 2: [(3,1)]
- 3: []
Reverse graph rg:
- 0: []
- 1: [(0,2)]
- 2: [(0,5), (1,1)]
- 3: [(1,3), (2,1)]

Step 2: Run Dijkstra from src1 = 0 Starting from node 0, we find shortest paths to all nodes:

d1[0] = 0 (start node)
d1[1] = 2 (path: 0→1)
d1[2] = 3 (path: 0→1→2, cost 2+1=3, better than direct 0→2 with cost 5)
d1[3] = 4 (path: 0→1→2→3, cost 2+1+1=4)

Step 3: Run Dijkstra from src2 = 1 Starting from node 1, we find shortest paths to all nodes:

d2[0] = ∞ (no path from 1 to 0)
d2[1] = 0 (start node)
d2[2] = 1 (path: 1→2)
d2[3] = 2 (path: 1→2→3, cost 1+1=2, better than direct 1→3 with cost 3)

Step 4: Run Dijkstra from dest = 3 on reverse graph This gives us distances from each node to dest in the original graph:

d3[0] = 4 (in original: 0→1→2→3)
d3[1] = 2 (in original: 1→2→3)
d3[2] = 1 (in original: 2→3)
d3[3] = 0 (destination node)

Step 5: Calculate total weights for each potential meeting point For each node i, calculate d1[i] + d2[i] + d3[i]:

Node 0: 0 + ∞ + 4 = ∞ (invalid - src2 can't reach node 0)
Node 1: 2 + 0 + 2 = 4
Node 2: 3 + 1 + 1 = 5
Node 3: 4 + 2 + 0 = 6

Step 6: Find the minimum The minimum value is 4, achieved when node 1 is the meeting point.

This means the optimal subgraph consists of:

Path from src1 (0) to node 1: edge 0→1 (weight 2)
Path from src2 (1) to node 1: no edges needed (already at node 1)
Path from node 1 to dest (3): edges 1→2 and 2→3 (weights 1 + 1 = 2)

Total weight = 2 + 0 + 2 = 4

The selected edges form a subgraph where both src1 and src2 can reach dest with minimum total edge weight of 4.

Solution Implementation

1from collections import defaultdict
2from heapq import heappush, heappop
3from typing import List
4from math import inf
5
6
7class Solution:
8    def minimumWeight(
9        self, n: int, edges: List[List[int]], src1: int, src2: int, dest: int
10    ) -> int:
11        """
12        Find the minimum total weight for paths from src1 and src2 to dest,
13        where both paths can meet at any intermediate node.
14      
15        Args:
16            n: Number of nodes in the graph
17            edges: List of [from_node, to_node, weight] representing directed edges
18            src1: First source node
19            src2: Second source node
20            dest: Destination node
21          
22        Returns:
23            Minimum total weight, or -1 if no valid path exists
24        """
25      
26        def dijkstra(graph: defaultdict, start_node: int) -> List[float]:
27            """
28            Compute shortest distances from start_node to all other nodes.
29          
30            Args:
31                graph: Adjacency list representation of the graph
32                start_node: Starting node for shortest path computation
33              
34            Returns:
35                List of shortest distances from start_node to each node
36            """
37            # Initialize distances with infinity
38            distances = [inf] * n
39            distances[start_node] = 0
40          
41            # Priority queue: (distance, node)
42            priority_queue = [(0, start_node)]
43          
44            while priority_queue:
45                current_distance, current_node = heappop(priority_queue)
46              
47                # Skip if we've already found a better path to this node
48                if current_distance > distances[current_node]:
49                    continue
50              
51                # Explore neighbors
52                for neighbor, edge_weight in graph[current_node]:
53                    new_distance = distances[current_node] + edge_weight
54                  
55                    # Update distance if we found a shorter path
56                    if distances[neighbor] > new_distance:
57                        distances[neighbor] = new_distance
58                        heappush(priority_queue, (new_distance, neighbor))
59          
60            return distances
61      
62        # Build forward graph and reverse graph
63        forward_graph = defaultdict(list)
64        reverse_graph = defaultdict(list)
65      
66        for from_node, to_node, weight in edges:
67            forward_graph[from_node].append((to_node, weight))
68            reverse_graph[to_node].append((from_node, weight))
69      
70        # Compute shortest distances from src1 to all nodes
71        distances_from_src1 = dijkstra(forward_graph, src1)
72      
73        # Compute shortest distances from src2 to all nodes
74        distances_from_src2 = dijkstra(forward_graph, src2)
75      
76        # Compute shortest distances from all nodes to dest (using reverse graph)
77        distances_to_dest = dijkstra(reverse_graph, dest)
78      
79        # Find minimum total weight by considering each node as meeting point
80        # Total weight = distance(src1 -> node) + distance(src2 -> node) + distance(node -> dest)
81        min_total_weight = min(
82            dist1 + dist2 + dist3 
83            for dist1, dist2, dist3 in zip(distances_from_src1, distances_from_src2, distances_to_dest)
84        )
85      
86        # Return -1 if no valid path exists, otherwise return the minimum weight
87        return -1 if min_total_weight >= inf else min_total_weight
88

1class Solution {
2    private static final Long INF = Long.MAX_VALUE;
3
4    /**
5     * Finds the minimum total weight path where two sources can meet at any intermediate node
6     * and then reach the destination together.
7     * 
8     * @param n Number of nodes in the graph
9     * @param edges Array of edges where each edge is [from, to, weight]
10     * @param src1 First source node
11     * @param src2 Second source node
12     * @param dest Destination node
13     * @return Minimum total weight, or -1 if no valid path exists
14     */
15    public long minimumWeight(int n, int[][] edges, int src1, int src2, int dest) {
16        // Build adjacency list for forward graph
17        List<Pair<Integer, Long>>[] forwardGraph = new List[n];
18        // Build adjacency list for reverse graph (for backward traversal from destination)
19        List<Pair<Integer, Long>>[] reverseGraph = new List[n];
20      
21        // Initialize adjacency lists
22        for (int i = 0; i < n; i++) {
23            forwardGraph[i] = new ArrayList<>();
24            reverseGraph[i] = new ArrayList<>();
25        }
26      
27        // Populate both forward and reverse graphs
28        for (int[] edge : edges) {
29            int from = edge[0];
30            int to = edge[1];
31            long weight = edge[2];
32          
33            // Add edge to forward graph
34            forwardGraph[from].add(new Pair<>(to, weight));
35            // Add reversed edge to reverse graph
36            reverseGraph[to].add(new Pair<>(from, weight));
37        }
38      
39        // Calculate shortest distances from src1 to all nodes
40        long[] distancesFromSrc1 = dijkstra(forwardGraph, src1);
41        // Calculate shortest distances from src2 to all nodes
42        long[] distancesFromSrc2 = dijkstra(forwardGraph, src2);
43        // Calculate shortest distances from all nodes to dest (using reverse graph)
44        long[] distancesToDest = dijkstra(reverseGraph, dest);
45      
46        long minWeight = -1;
47      
48        // Try each node as a potential meeting point
49        for (int meetingPoint = 0; meetingPoint < n; meetingPoint++) {
50            // Skip if any path segment is unreachable
51            if (distancesFromSrc1[meetingPoint] == INF || 
52                distancesFromSrc2[meetingPoint] == INF || 
53                distancesToDest[meetingPoint] == INF) {
54                continue;
55            }
56          
57            // Calculate total weight: src1->meeting + src2->meeting + meeting->dest
58            long totalWeight = distancesFromSrc1[meetingPoint] + 
59                              distancesFromSrc2[meetingPoint] + 
60                              distancesToDest[meetingPoint];
61          
62            // Update minimum weight if this is better
63            if (minWeight == -1 || minWeight > totalWeight) {
64                minWeight = totalWeight;
65            }
66        }
67      
68        return minWeight;
69    }
70
71    /**
72     * Implements Dijkstra's algorithm to find shortest paths from a source node.
73     * 
74     * @param graph Adjacency list representation of the graph
75     * @param source Starting node for shortest path calculation
76     * @return Array of shortest distances from source to all nodes
77     */
78    private long[] dijkstra(List<Pair<Integer, Long>>[] graph, int source) {
79        int nodeCount = graph.length;
80        long[] distances = new long[nodeCount];
81        Arrays.fill(distances, INF);
82        distances[source] = 0;
83      
84        // Priority queue to process nodes by minimum distance
85        // Pair format: (distance, node)
86        PriorityQueue<Pair<Long, Integer>> priorityQueue = 
87            new PriorityQueue<>(Comparator.comparingLong(Pair::getKey));
88        priorityQueue.offer(new Pair<>(0L, source));
89      
90        while (!priorityQueue.isEmpty()) {
91            Pair<Long, Integer> current = priorityQueue.poll();
92            long currentDistance = current.getKey();
93            int currentNode = current.getValue();
94          
95            // Skip if we've already found a better path to this node
96            if (currentDistance > distances[currentNode]) {
97                continue;
98            }
99          
100            // Explore all neighbors
101            for (Pair<Integer, Long> edge : graph[currentNode]) {
102                int neighbor = edge.getKey();
103                long edgeWeight = edge.getValue();
104              
105                // Check if we found a shorter path to the neighbor
106                if (distances[neighbor] > distances[currentNode] + edgeWeight) {
107                    distances[neighbor] = distances[currentNode] + edgeWeight;
108                    priorityQueue.offer(new Pair<>(distances[neighbor], neighbor));
109                }
110            }
111        }
112      
113        return distances;
114    }
115}
116

1class Solution {
2private:
3    static constexpr long long INF = LLONG_MAX;
4  
5    /**
6     * Implements Dijkstra's algorithm to find shortest paths from a source node.
7     * 
8     * @param graph Adjacency list representation of the graph
9     * @param source Starting node for shortest path calculation
10     * @return Vector of shortest distances from source to all nodes
11     */
12    vector<long long> dijkstra(const vector<vector<pair<int, long long>>>& graph, int source) {
13        int node_count = graph.size();
14        vector<long long> distances(node_count, INF);
15        distances[source] = 0;
16      
17        // Priority queue to process nodes by minimum distance
18        // Pair format: (distance, node)
19        priority_queue<pair<long long, int>, 
20                      vector<pair<long long, int>>, 
21                      greater<pair<long long, int>>> pq;
22        pq.push({0LL, source});
23      
24        while (!pq.empty()) {
25            auto [current_distance, current_node] = pq.top();
26            pq.pop();
27          
28            // Skip if we've already found a better path to this node
29            if (current_distance > distances[current_node]) {
30                continue;
31            }
32          
33            // Explore all neighbors
34            for (const auto& [neighbor, edge_weight] : graph[current_node]) {
35                // Check if we found a shorter path to the neighbor
36                if (distances[neighbor] > distances[current_node] + edge_weight) {
37                    distances[neighbor] = distances[current_node] + edge_weight;
38                    pq.push({distances[neighbor], neighbor});
39                }
40            }
41        }
42      
43        return distances;
44    }
45  
46public:
47    /**
48     * Finds the minimum total weight path where two sources can meet at any intermediate node
49     * and then reach the destination together.
50     * 
51     * @param n Number of nodes in the graph
52     * @param edges Vector of edges where each edge is [from, to, weight]
53     * @param src1 First source node
54     * @param src2 Second source node
55     * @param dest Destination node
56     * @return Minimum total weight, or -1 if no valid path exists
57     */
58    long long minimumWeight(int n, vector<vector<int>>& edges, int src1, int src2, int dest) {
59        // Build adjacency list for forward graph
60        vector<vector<pair<int, long long>>> forward_graph(n);
61        // Build adjacency list for reverse graph (for backward traversal from destination)
62        vector<vector<pair<int, long long>>> reverse_graph(n);
63      
64        // Populate both forward and reverse graphs
65        for (const auto& edge : edges) {
66            int from = edge[0];
67            int to = edge[1];
68            long long weight = edge[2];
69          
70            // Add edge to forward graph
71            forward_graph[from].push_back({to, weight});
72            // Add reversed edge to reverse graph
73            reverse_graph[to].push_back({from, weight});
74        }
75      
76        // Calculate shortest distances from src1 to all nodes
77        vector<long long> distances_from_src1 = dijkstra(forward_graph, src1);
78        // Calculate shortest distances from src2 to all nodes
79        vector<long long> distances_from_src2 = dijkstra(forward_graph, src2);
80        // Calculate shortest distances from all nodes to dest (using reverse graph)
81        vector<long long> distances_to_dest = dijkstra(reverse_graph, dest);
82      
83        long long min_weight = -1;
84      
85        // Try each node as a potential meeting point
86        for (int meeting_point = 0; meeting_point < n; meeting_point++) {
87            // Skip if any path segment is unreachable
88            if (distances_from_src1[meeting_point] == INF || 
89                distances_from_src2[meeting_point] == INF || 
90                distances_to_dest[meeting_point] == INF) {
91                continue;
92            }
93          
94            // Calculate total weight: src1->meeting + src2->meeting + meeting->dest
95            long long total_weight = distances_from_src1[meeting_point] + 
96                                    distances_from_src2[meeting_point] + 
97                                    distances_to_dest[meeting_point];
98          
99            // Update minimum weight if this is better
100            if (min_weight == -1 || min_weight > total_weight) {
101                min_weight = total_weight;
102            }
103        }
104      
105        return min_weight;
106    }
107};
108

1const INF = Number.MAX_SAFE_INTEGER;
2
3/**
4 * Finds the minimum total weight path where two sources can meet at any intermediate node
5 * and then reach the destination together.
6 * 
7 * @param n Number of nodes in the graph
8 * @param edges Array of edges where each edge is [from, to, weight]
9 * @param src1 First source node
10 * @param src2 Second source node
11 * @param dest Destination node
12 * @return Minimum total weight, or -1 if no valid path exists
13 */
14function minimumWeight(n: number, edges: number[][], src1: number, src2: number, dest: number): number {
15    // Build adjacency list for forward graph
16    const forwardGraph: Array<Array<[number, number]>> = Array(n).fill(null).map(() => []);
17    // Build adjacency list for reverse graph (for backward traversal from destination)
18    const reverseGraph: Array<Array<[number, number]>> = Array(n).fill(null).map(() => []);
19  
20    // Populate both forward and reverse graphs
21    for (const edge of edges) {
22        const from = edge[0];
23        const to = edge[1];
24        const weight = edge[2];
25      
26        // Add edge to forward graph
27        forwardGraph[from].push([to, weight]);
28        // Add reversed edge to reverse graph
29        reverseGraph[to].push([from, weight]);
30    }
31  
32    // Calculate shortest distances from src1 to all nodes
33    const distancesFromSrc1 = dijkstra(forwardGraph, src1);
34    // Calculate shortest distances from src2 to all nodes
35    const distancesFromSrc2 = dijkstra(forwardGraph, src2);
36    // Calculate shortest distances from all nodes to dest (using reverse graph)
37    const distancesToDest = dijkstra(reverseGraph, dest);
38  
39    let minWeight = -1;
40  
41    // Try each node as a potential meeting point
42    for (let meetingPoint = 0; meetingPoint < n; meetingPoint++) {
43        // Skip if any path segment is unreachable
44        if (distancesFromSrc1[meetingPoint] === INF || 
45            distancesFromSrc2[meetingPoint] === INF || 
46            distancesToDest[meetingPoint] === INF) {
47            continue;
48        }
49      
50        // Calculate total weight: src1->meeting + src2->meeting + meeting->dest
51        const totalWeight = distancesFromSrc1[meetingPoint] + 
52                          distancesFromSrc2[meetingPoint] + 
53                          distancesToDest[meetingPoint];
54      
55        // Update minimum weight if this is better
56        if (minWeight === -1 || minWeight > totalWeight) {
57            minWeight = totalWeight;
58        }
59    }
60  
61    return minWeight;
62}
63
64/**
65 * Implements Dijkstra's algorithm to find shortest paths from a source node.
66 * 
67 * @param graph Adjacency list representation of the graph
68 * @param source Starting node for shortest path calculation
69 * @return Array of shortest distances from source to all nodes
70 */
71function dijkstra(graph: Array<Array<[number, number]>>, source: number): number[] {
72    const nodeCount = graph.length;
73    const distances: number[] = new Array(nodeCount).fill(INF);
74    distances[source] = 0;
75  
76    // Priority queue to process nodes by minimum distance
77    // Using MinPriorityQueue from @datastructures-js/priority-queue or implementing with array
78    // For simplicity, using array with custom sorting (less efficient but works)
79    const priorityQueue: Array<[number, number]> = []; // [distance, node]
80    priorityQueue.push([0, source]);
81  
82    while (priorityQueue.length > 0) {
83        // Sort to get minimum distance first (simulating priority queue)
84        priorityQueue.sort((a, b) => a[0] - b[0]);
85        const current = priorityQueue.shift()!;
86        const currentDistance = current[0];
87        const currentNode = current[1];
88      
89        // Skip if we've already found a better path to this node
90        if (currentDistance > distances[currentNode]) {
91            continue;
92        }
93      
94        // Explore all neighbors
95        for (const edge of graph[currentNode]) {
96            const neighbor = edge[0];
97            const edgeWeight = edge[1];
98          
99            // Check if we found a shorter path to the neighbor
100            if (distances[neighbor] > distances[currentNode] + edgeWeight) {
101                distances[neighbor] = distances[currentNode] + edgeWeight;
102                priorityQueue.push([distances[neighbor], neighbor]);
103            }
104        }
105    }
106  
107    return distances;
108}
109

Time and Space Complexity

Time Complexity: O((V + E) * log V)

The algorithm performs three Dijkstra's shortest path computations:

Two from source nodes (src1 and src2) using the original graph g
One from the destination node using the reverse graph rg

Each Dijkstra implementation has a time complexity of O((V + E) * log V) where:

V = n (number of vertices)
E is the number of edges
The heap operations (heappush and heappop) take O(log V) time
Each edge is processed at most once, resulting in at most E heap operations
Each vertex is extracted from the heap at most once, resulting in at most V heap operations

Since we run Dijkstra three times, the overall time complexity is 3 * O((V + E) * log V) = O((V + E) * log V).

The final loop to find the minimum sum iterates through n vertices once, which is O(n) and doesn't affect the overall complexity.

Space Complexity: O(V + E)

The space requirements include:

Graph representation g: O(E) to store all edges
Reverse graph rg: O(E) to store all edges in reverse
Three distance arrays (d1, d2, d3): 3 * O(V) = O(V)
Priority queue in Dijkstra: O(V) in the worst case
Recursive call stack: Not applicable as the implementation is iterative

The dominant space complexity is O(V + E) for storing the graph structures and distance arrays.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to Handle the Reverse Graph for Distance to Destination

Pitfall: A common mistake is trying to compute distances from all nodes to the destination using the forward graph. Since the graph is directed, you cannot simply run Dijkstra from each node to find distances to the destination - this would be inefficient and incorrect.

Why it happens: It's intuitive to think about running Dijkstra from the destination node in the forward graph, but this gives you distances FROM the destination TO all other nodes, not the other way around.

Incorrect approach:

# WRONG: This computes distances FROM dest TO all nodes
distances_to_dest = dijkstra(forward_graph, dest)

Correct solution: Build a reverse graph where all edges are flipped, then run Dijkstra from the destination. This effectively computes distances from all nodes to the destination:

# Build reverse graph
reverse_graph = defaultdict(list)
for from_node, to_node, weight in edges:
    reverse_graph[to_node].append((from_node, weight))

# Now this correctly computes distances FROM all nodes TO dest
distances_to_dest = dijkstra(reverse_graph, dest)

2. Not Checking for Already Processed Nodes in Dijkstra

Pitfall: Processing the same node multiple times in Dijkstra when it appears in the priority queue with different distances.

Why it happens: The priority queue might contain multiple entries for the same node with different distances. Without checking, you might process outdated entries.

Incorrect approach:

def dijkstra(graph, start_node):
    distances = [inf] * n
    distances[start_node] = 0
    priority_queue = [(0, start_node)]
  
    while priority_queue:
        current_distance, current_node = heappop(priority_queue)
        # MISSING: Check if this is an outdated entry
      
        for neighbor, edge_weight in graph[current_node]:
            new_distance = distances[current_node] + edge_weight
            if distances[neighbor] > new_distance:
                distances[neighbor] = new_distance
                heappush(priority_queue, (new_distance, neighbor))

Correct solution: Skip processing if the current distance from the queue is greater than the already recorded distance:

while priority_queue:
    current_distance, current_node = heappop(priority_queue)
  
    # Skip if we've already found a better path
    if current_distance > distances[current_node]:
        continue
  
    # ... rest of the algorithm

3. Integer Overflow or Incorrect Infinity Handling

Pitfall: Using a fixed large number instead of float('inf') can cause overflow when adding distances, or the "infinity" value might be too small for the actual edge weights in the problem.

Incorrect approach:

# Using a fixed "large" number
INF = 10**9
distances = [INF] * n

# Later in the code:
min_weight = min(d1[i] + d2[i] + d3[i] for i in range(n))
# If all three are INF (10^9), sum is 3*10^9, which might cause issues

Correct solution: Use Python's float('inf') which handles arithmetic operations correctly:

from math import inf

distances = [inf] * n
# inf + inf + inf = inf (handled correctly)
# inf >= inf evaluates to True

4. Not Considering Edge Cases for the Meeting Point

Pitfall: Assuming the meeting point must be different from source or destination nodes.

Why it happens: It's easy to think the paths must "meet in the middle," but the optimal meeting point could be:

At src1 (if src2 goes through src1 to reach dest)
At src2 (if src1 goes through src2 to reach dest)
At dest (both sources go directly to destination)

Solution: The code correctly considers ALL nodes (0 to n-1) as potential meeting points, including the source and destination nodes themselves:

# Correctly checks all nodes as potential meeting points
min_total_weight = min(
    dist1 + dist2 + dist3 
    for dist1, dist2, dist3 in zip(distances_from_src1, distances_from_src2, distances_to_dest)
)

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

The three-steps of Depth First Search are:

Identify states;
Draw the state-space tree;
DFS on the state-space tree.

True

False

I don't know

2203. Minimum Weighted Subgraph With the Required Paths

Problem Description

Intuition

Solution Approach

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Example Walkthrough

Solution Implementation

Time and Space Complexity

Common Pitfalls

1. Forgetting to Handle the Reverse Graph for Distance to Destination

2. Not Checking for Already Processed Nodes in Dijkstra

3. Integer Overflow or Incorrect Infinity Handling

4. Not Considering Edge Cases for the Meeting Point

Recommended Readings