#3123

Hard

auto_awesomeGraph traversal with depth-first search

LeetCode Problem Workspace

Find Edges in Shortest Paths

Use two Dijkstra runs to mark exactly which edges can appear on at least one shortest path from 0 to n - 1.

depth first search breadth first search graph heap priority queue shortest path

Problem Statement

You are given an undirected weighted graph with nodes numbered from 0 to n - 1 and an edge list where each entry stores two endpoints and a positive weight. Your task is not to return one shortest path. Instead, you must decide for every original edge whether it appears in at least one minimum-cost path from node 0 to node n - 1.

Return a boolean array aligned with the input edge order. Mark an entry true when that edge can lie on some shortest route from the start to the destination, and false when every use of that edge would make the path longer than the optimum.

Examples

Example 1

Input: 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]]

Output: [true,true,true,false,true,true,true,false]

The following are all the shortest paths between nodes 0 and 5:

Example 2

Input: n = 4, edges = [[2,0,1],[0,1,1],[0,3,4],[3,2,2]]

Output: [true,false,false,true]

There is one shortest path between nodes 0 and 3, which is the path 0 -> 2 -> 3 with the sum of weights 1 + 2 = 3 .

Constraints

2 <= n <= 5 * 104
m == edges.length
1 <= m <= min(5 * 104, n * (n - 1) / 2)
0 <= ai, bi < n
ai != bi
1 <= wi <= 105
There are no repeated edges.

Solution Approach

Run shortest path from both ends

Build an adjacency list with neighbor, weight, and edge index. Run Dijkstra from node 0 to get distFromStart, then run Dijkstra again from node n - 1 to get distFromEnd. This is the key pattern in Find Edges in Shortest Paths: one distance array tells you cost before an edge, and the other tells you cost after it.

Check each edge against the global optimum

Let best = distFromStart[n - 1]. For an undirected edge (u, v, w), mark it true if distFromStart[u] + w + distFromEnd[v] == best or distFromStart[v] + w + distFromEnd[u] == best. Testing both directions matters because the edge can be used in either orientation along a shortest path.

Why DFS or BFS alone is not enough here

A plain DFS can enumerate too many paths, and BFS only works for unweighted graphs or equal edge costs. The useful graph traversal step comes after Dijkstra: once shortest distances are known, you are effectively validating whether an edge sits on the shortest-path DAG defined by those distance equations.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Using Dijkstra twice with a priority queue takes O((n + m) log n) time and O(n + m) space. The final edge scan is O(m). This is the right trade-off for n and m up to 5 * 10^4 because any approach that tries to list all shortest paths can blow up even when the answer array is small.

What Interviewers Usually Probe

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

Common Pitfalls or Variants

Common pitfalls

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

Follow-up variants

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

FAQ

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.

terminal

Solution

Solution 1: Heap Optimized Dijkstra

First, we create an adjacency list $g$ to store the edges of the graph. Then we create an array $dist$ to store the shortest distance from node $0$ to other nodes. We initialize $dist[0] = 0$, and the distance of other nodes is initialized to infinity.

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 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

Continue Practicing

#3286 find a safe walk through a grid #3419 minimize the maximum edge weight of graph #3607 power grid maintenance