What is the core trick in Find Edges in Shortest Paths?

Compute shortest distances from the source and from the destination, then check whether an edge can connect the two halves of an optimal route exactly. That turns path membership into a local equation per edge.

Why is Dijkstra better than DFS for this problem's graph traversal pattern?

DFS can search exponentially many weighted paths before it proves anything. Dijkstra gives the minimum prefix and suffix costs first, so each edge can be judged in O(1) afterward.

Why do I need distances from node n - 1 too?

Knowing only the cost to reach an edge is not enough. You also need the cheapest cost from the far endpoint to the destination to confirm that using the edge still lands on the global shortest total.

Can an edge be true even if it is not on every shortest path?

Yes. The answer is true when the edge appears on at least one shortest path. This problem is about union over all shortest paths, not intersection.

How do I know the edge check is correct?

For an edge (u, v, w), it is valid when one direction satisfies distFromStart[u] + w + distFromEnd[v] == distFromStart[n - 1] or the symmetric version with u and v swapped. That equality means the edge fits perfectly inside a full shortest path.

#3123

Hard

auto_awesome图·DFS·traversal

LeetCode 题解工作台

最短路径中的边

给你一个 n 个节点的无向带权图，节点编号为 0 到 n - 1 。图中总共有 m 条边，用二维数组 edges 表示，其中 edges[i] = [a i , b i , w i ] 表示节点 a i 和 b i 之间有一条边权为 w i 的边。对于节点 0 为出发点，节点 n - 1 为结束点…

深度优先搜索广度优先搜索图堆（优先队列）最短路径

题目描述

给你一个 n 个节点的无向带权图，节点编号为 0 到 n - 1 。图中总共有 m 条边，用二维数组 edges 表示，其中 edges[i] = [a_i, b_i, w_i] 表示节点 a_i 和 b_i 之间有一条边权为 w_i 的边。

对于节点 0 为出发点，节点 n - 1 为结束点的所有最短路，你需要返回一个长度为 m 的 boolean 数组 answer ，如果 edges[i] 至少在其中一条最短路上，那么 answer[i] 为 true ，否则 answer[i] 为 false 。

请你返回数组 answer 。

注意，图可能不连通。

示例 1：

输入：n = 6, edges = [[0,1,4],[0,2,1],[1,3,2],[1,4,3],[1,5,1],[2,3,1],[3,5,3],[4,5,2]]

输出：[true,true,true,false,true,true,true,false]

解释：

以下为节点 0 出发到达节点 5 的所有最短路：

路径 0 -> 1 -> 5 ：边权和为 4 + 1 = 5 。
路径 0 -> 2 -> 3 -> 5 ：边权和为 1 + 1 + 3 = 5 。
路径 0 -> 2 -> 3 -> 1 -> 5 ：边权和为 1 + 1 + 2 + 1 = 5 。

示例 2：

输入：n = 4, edges = [[2,0,1],[0,1,1],[0,3,4],[3,2,2]]

输出：[true,false,false,true]

解释：

只有一条从节点 0 出发到达节点 3 的最短路 0 -> 2 -> 3 ，边权和为 1 + 2 = 3 。

提示：

2 <= n <= 5 * 10⁴
m == edges.length
1 <= m <= min(5 * 10⁴, n * (n - 1) / 2)
0 <= a_i, b_i < n
a_i != b_i
1 <= w_i <= 10⁵
图中没有重边。

lightbulb

解题思路

方法一：堆优化的 Dijkstra

我们先创建一个邻接表 $g$ ，用于存储图的边。然后创建一个数组 $dist$ ，用于存储从节点 $0$ 到其他节点的最短距离。初始化 $dist[0] = 0$ ，其余节点的距离初始化为无穷大。

然后，我们使用 Dijkstra 算法计算从节点 $0$ 到其他节点的最短距离。具体步骤如下：

创建一个优先队列 $q$ ，用于存储节点的距离和节点编号，初始时将节点 $0$ 加入队列，距离为 $0$ 。
从队列中取出一个节点 $a$ ，如果 $a$ 的距离 $da$ 大于 $dist[a]$ ，说明 $a$ 已经被更新过了，直接跳过。
遍历节点 $a$ 的所有邻居节点 $b$ ，如果 $dist[b] > dist[a] + w$ ，则更新 $dist[b] = dist[a] + w$ ，并将节点 $b$ 加入队列。
重复步骤 2 和步骤 3，直到队列为空。

接着，我们创建一个长度为 $m$ 的答案数组 $ans$ ，初始时所有元素都为 $false$ 。如果 $dist[n - 1]$ 为无穷大，说明节点 $0$ 无法到达节点 $n - 1$ ，直接返回 $ans$ 。否则，我们从节点 $n - 1$ 开始，遍历所有的边，如果边 $(a, b, i)$ 满足 $dist[a] = dist[b] + w$ ，则将 $ans[i]$ 置为 $true$ ，并将节点 $b$ 加入队列。

最后，返回答案即可。

时间复杂度 $O(m \times \log m)$ ，空间复杂度 $O(n + m)$ ，其中 $n$ 和 $m$ 分别为节点数和边数。

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

30

class Solution:
    def findAnswer(self, n: int, edges: List[List[int]]) -> List[bool]:
        g = defaultdict(list)
        for i, (a, b, w) in enumerate(edges):
            g[a].append((b, w, i))
            g[b].append((a, w, i))
        dist = [inf] * n
        dist[0] = 0
        q = [(0, 0)]
        while q:
            da, a = heappop(q)
            if da > dist[a]:
                continue
            for b, w, _ in g[a]:
                if dist[b] > dist[a] + w:
                    dist[b] = dist[a] + w
                    heappush(q, (dist[b], b))
        m = len(edges)
        ans = [False] * m
        if dist[n - 1] == inf:
            return ans
        q = deque([n - 1])
        while q:
            a = q.popleft()
            for b, w, i in g[a]:
                if dist[a] == dist[b] + w:
                    ans[i] = True
                    q.append(b)
        return ans

speed

复杂度分析

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

psychology

面试官常问的追问

外企场景

question_mark
They mention shortest paths from both node 0 and node n - 1, which points directly to dual Dijkstra distances.
question_mark
They care about whether an edge is on any shortest path, not about reconstructing one path, so edge validation is enough.
question_mark
They highlight weighted edges and large constraints, which rules out BFS layering and brute-force DFS enumeration.

warning

常见陷阱

外企场景

error
Running BFS because the graph is undirected, then getting wrong answers when weights differ.
error
Only checking distFromStart[u] + w + distFromEnd[v] and forgetting the reverse orientation of the same undirected edge.
error
Trying to store every predecessor path explicitly, which can explode on graphs with many tied shortest routes.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Return all nodes that lie on at least one shortest path by checking distFromStart[x] + distFromEnd[x] == best.
arrow_right_alt
Count how many shortest paths use each edge, which requires DP over the shortest-path DAG instead of a simple boolean test.
arrow_right_alt
Handle a directed version where each edge is checked in only its original direction after forward and reverse shortest-path runs.

help

常见问题

外企场景

继续练习

#3286 穿越网格图的安全路径 #3419 图的最大边权的最小值 #3607 电网维护