Tejav
#2203

Minimum Weighted Subgraph With the Required Paths

Hard
Graph TheoryHeap (Priority Queue)Shortest PathDijkstra's AlgorithmGraph TraversalShortest Path
LeetCode ↗

Approaches

Brute ForceOptimal
Complexity Comparison
Brute ForceOptimal Solution★
Time
O(n²)
O(n log n + e log n)
Space
O(1)
O(n + e)
💡

Intuition

Time O(n log n + e log n)Space O(n + e)

The optimal solution leverages Dijkstra's algorithm to find the shortest paths from src1 and src2 to all nodes, and then identifies the common nodes where paths converge to dest. This significantly reduces the number of combinations we need to check.

⚙️

Algorithm

3 steps
  1. 1Step 1: Use Dijkstra's algorithm to find the shortest path from src1 to all nodes and from src2 to all nodes.
  2. 2Step 2: For each node, calculate the total weight of the edges needed to reach dest from that node using the paths found in Step 1.
  3. 3Step 3: Return the minimum total weight found across all nodes, or -1 if no valid path exists.
solution.py30 lines
1# Full working Python code
2import heapq
3
4
5def dijkstra(n, edges, src):
6    graph = {i: [] for i in range(n)}
7    for u, v, w in edges:
8        graph[u].append((v, w))
9    dist = {i: float('inf') for i in range(n)}
10    dist[src] = 0
11    pq = [(0, src)]
12    while pq:
13        curr_dist, node = heapq.heappop(pq)
14        if curr_dist > dist[node]: continue
15        for neighbor, weight in graph[node]:
16            if curr_dist + weight < dist[neighbor]:
17                dist[neighbor] = curr_dist + weight
18                heapq.heappush(pq, (dist[neighbor], neighbor))
19    return dist
20
21
22def minWeightSubgraph(n, edges, src1, src2, dest):
23    dist1 = dijkstra(n, edges, src1)
24    dist2 = dijkstra(n, edges, src2)
25    min_weight = float('inf')
26    for u, v, w in edges:
27        total_weight = dist1[u] + dist2[v] + w
28        if dist1[u] < float('inf') and dist2[v] < float('inf'):
29            min_weight = min(min_weight, total_weight)
30    return min_weight if min_weight != float('inf') else -1
ℹ

Complexity note: Dijkstra's algorithm runs in O((n + e) log n) time, where e is the number of edges. We store distances for all nodes, leading to O(n) space complexity.

  • 1The optimal solution relies on finding common nodes where paths from src1 and src2 converge to dest.
  • 2Using Dijkstra's algorithm allows us to efficiently compute shortest paths without checking all combinations.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.