2203. Minimum Weighted Subgraph With the Required Paths

How to solve Minimum Weighted Subgraph With the Required Paths (LeetCode 2203): the approach in brief

The problem

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.

Pattern

Minimum Weighted Subgraph With the Required Paths is a Graph Traversal Patterns (DFS & BFS) problem, in the Shortest Path (Dijkstra's Algorithm) subpattern. The pattern covers DFS/BFS traversal, topological sort, shortest paths, Union-Find, and MST

Master Dijkstra's algorithm for finding shortest paths in weighted graphs with non-negative edges.

Approach outline

1. Consider what the paths from src1 to dest and src2 to dest would look like in the optimal solution.
2. It can be shown that in an optimal solution, the two paths from src1 and src2 will coincide at one node, and the remaining part to dest will be the same for both paths. Now consider how to find the node where the paths will coincide.
3. How can algorithms for finding the shortest path between two nodes help us?

Complexity

The reference solution runs in O((n + m) * log n) time and O(n + m) space.