What is the main pattern to focus on for the 'Minimum Weighted Subgraph With the Required Paths' problem?

The problem combines graph traversal techniques with shortest path algorithms, requiring candidates to efficiently find the minimum weighted subgraph connecting three specific nodes.

Which algorithms are best for solving the 'Minimum Weighted Subgraph With the Required Paths' problem?

Dijkstra’s algorithm or Bellman-Ford are suitable for finding the shortest paths. The choice depends on the presence of negative edge weights in the graph.

What happens if no valid subgraph exists in the 'Minimum Weighted Subgraph With the Required Paths' problem?

If no valid subgraph exists, the correct solution is to return -1, as no paths from src1 to dest or src2 to dest are possible.

How do I optimize my solution for large graphs in the 'Minimum Weighted Subgraph With the Required Paths' problem?

Optimization can be achieved by using efficient shortest path algorithms like Dijkstra's with priority queues, reducing the complexity for large graphs.

What edge cases should I consider when solving the 'Minimum Weighted Subgraph With the Required Paths' problem?

Consider edge cases where no valid paths exist between the nodes, as well as situations where the graph is sparse or contains negative weight edges.

#2203

Hard

auto_awesome图

LeetCode 题解工作台

包含要求路径的最小带权子图

给你一个整数 n ，它表示一个带权有向图的节点数，节点编号为 0 到 n - 1 。同时给你一个二维整数数组 edges ，其中 edges[i] = [from i , to i , weight i ] ，表示从 from i 到 to i 有一条边权为 weight i 的有向边。 …

图最短路径

题目描述

给你一个整数 n ，它表示一个 带权有向 图的节点数，节点编号为 0 到 n - 1 。

同时给你一个二维整数数组 edges ，其中 edges[i] = [from_i, to_i, weight_i] ，表示从 from_i 到 to_i 有一条边权为 weight_i 的有向边。

最后，给你三个 互不相同 的整数 src1 ，src2 和 dest ，表示图中三个不同的点。

请你从图中选出一个 边权和最小 的子图，使得从 src1 和 src2 出发，在这个子图中，都可以到达 dest 。如果这样的子图不存在，请返回 -1 。

子图中的点和边都应该属于原图的一部分。子图的边权和定义为它所包含的所有边的权值之和。

示例 1：

输入：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
输出：9
解释：
上图为输入的图。
蓝色边为最优子图之一。
注意，子图 [[1,0,3],[0,5,6]] 也能得到最优解，但无法在满足所有限制的前提下，得到更优解。

示例 2：

输入：n = 3, edges = [[0,1,1],[2,1,1]], src1 = 0, src2 = 1, dest = 2
输出：-1
解释：
上图为输入的图。
可以看到，不存在从节点 1 到节点 2 的路径，所以不存在任何子图满足所有限制。

提示：

3 <= n <= 10⁵
0 <= edges.length <= 10⁵
edges[i].length == 3
0 <= from_i, to_i, src1, src2, dest <= n - 1
from_i != to_i
src1 ，src2 和 dest 两两不同。
1 <= weight[i] <= 10⁵

lightbulb

解题思路

方法一：枚举三条最短路的交汇点

最短路问题。

我们假设从 $src1$ 出发到 $dest$ 的一条最短路径为 $A$ ，从 $src2$ 出发到 $dest$ 的一条最短路径为 $B$ 。

$A$ , $B$ 两条路径一定存在着公共点 $p$ ，因为 $dest$ 一定是其中一个公共点。那么问题可以转换为求以下三条路径和的最小值：

从 $src1$ 到 $p$ 的最短路
从 $src2$ 到 $p$ 的最短路
从 $p$ 到 $dest$ 的最短路（这里我们可以将原图的所有边反向，然后转换为从 $dest$ 到 $p$ 的最短路）

我们进行三次 Dijkstra 算法，就可以求出 $src1$ , $src2$ , $dest$ 到其他点的最短路径。

公共点可以有多个，因此我们在 $[0,n)$ 范围内枚举公共点 $p$ ，找出边权之和最小的值即可。

时间复杂度 $O(mlogn)$ ，其中 m 表示数组 $edges$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

class Solution:
    def minimumWeight(
        self, n: int, edges: List[List[int]], src1: int, src2: int, dest: int
    ) -> int:
        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

        g = defaultdict(list)
        rg = defaultdict(list)
        for f, t, w in edges:
            g[f].append((t, w))
            rg[t].append((f, w))
        d1 = dijkstra(g, src1)
        d2 = dijkstra(g, src2)
        d3 = dijkstra(rg, dest)
        ans = min(sum(v) for v in zip(d1, d2, d3))
        return -1 if ans >= inf else ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Candidates should discuss how to ensure that both paths (src1 to dest and src2 to dest) are captured in the subgraph.
question_mark
Watch for optimization techniques in graph filtering, focusing on minimizing unnecessary edges.
question_mark
Check if the candidate recognizes edge cases, such as no valid paths between the required nodes.

warning

常见陷阱

外企场景

error
Failing to consider edge cases where no path exists from src1 or src2 to dest.
error
Choosing the wrong shortest path algorithm for the given constraints.
error
Not properly minimizing the subgraph or including unnecessary edges in the solution.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Consider handling graphs with negative edge weights by using Bellman-Ford instead of Dijkstra’s algorithm.
arrow_right_alt
Challenge candidates with larger graphs, such as increasing the number of nodes and edges, to test algorithm efficiency.
arrow_right_alt
Introduce dynamic graph changes during the process to test how the solution adapts to updates.

help

常见问题

外企场景

继续练习

#2290 到达角落需要移除障碍物的最小数目 #2045 到达目的地的第二短时间 #1976 到达目的地的方案数