Skip to main content
Talentd

Find Edges in Shortest Paths - Solution & Explanation

HardDepth-First SearchBreadth-First SearchGraphHeap (Priority Queue)23 min readAsked at: DoorDash, WeRide
Practice this problem

Problem Statement

You are given an undirected weighted graph of n nodes numbered from 0 to n - 1. The graph consists of m edges represented by a 2D array edges, where edges[i] = [ai, bi, wi] indicates that there is an edge between nodes ai and bi with weight wi.

Consider all the shortest paths from node 0 to node n - 1 in the graph. You need to find a boolean array answer where answer[i] is true if the edge edges[i] is part of at least one shortest path. Otherwise, answer[i] is false.

Return the array answer.

Note that the graph may not be connected.

 

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]

Explanation:

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

  • The path 0 -> 1 -> 5: The sum of weights is 4 + 1 = 5.
  • The path 0 -> 2 -> 3 -> 5: The sum of weights is 1 + 1 + 3 = 5.
  • The path 0 -> 2 -> 3 -> 1 -> 5: The sum of weights is 1 + 1 + 2 + 1 = 5.

Example 2:

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

Output: [true,false,false,true]

Explanation:

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.

Approach Overview

Problem Overview: You are given a weighted graph and must determine which edges appear in at least one shortest path from node 0 to node n-1. Instead of returning the path itself, the goal is to mark every edge that can participate in any optimal route.

Approach 1: Double Dijkstra's Algorithm (O(E log V) time, O(V + E) space)

This approach runs Dijkstra twice. First compute the shortest distance from the source node 0 to every node. Then run Dijkstra again from the target node n-1 (conceptually on the reversed graph, though for undirected graphs the same adjacency list works). Let distStart[u] be the distance from the start and distEnd[v] be the distance from the end. For an edge (u, v, w), the edge belongs to some shortest path if distStart[u] + w + distEnd[v] == distStart[n-1] or the symmetric direction distStart[v] + w + distEnd[u] == distStart[n-1]. The key insight: any shortest path can be decomposed into prefix distance from the start, the edge weight, and suffix distance to the target. If their sum equals the global shortest distance, the edge lies on an optimal path. The heavy lifting is done by a min-heap implementation of priority queue inside Dijkstra. This method works efficiently on large sparse graphs.

Approach 2: Bellman-Ford with Inverse Relaxation (O(V * E) time, O(V + E) space)

This version starts by computing shortest distances from the source using the Bellman-Ford relaxation process. After the distances stabilize, examine each edge to see whether it preserves shortest-path consistency: an edge (u, v, w) is valid if dist[u] + w == dist[v] or dist[v] + w == dist[u]. These edges form a directed acyclic structure that represents all valid shortest-path transitions. Build this filtered graph and run a DFS or BFS from node 0 to find which edges can actually reach n-1. Only edges reachable in this constrained graph belong to some shortest path. Bellman-Ford avoids priority queues and works even if negative weights exist (as long as there are no negative cycles). It relies on repeated relaxation over the full edge list, a classic technique in shortest path problems.

Recommended for interviews: Double Dijkstra is the expected solution. It runs in O(E log V), scales well for dense inputs, and clearly demonstrates understanding of graph shortest path decomposition. Bellman-Ford is a good fallback if negative weights appear or if the interviewer explicitly asks for a relaxation-based approach.

Approach 1: Approach 1: Double Dijkstra's Algorithm

This approach uses Dijkstra's algorithm twice. First, compute the shortest paths from the start node (0) to all other nodes. Then compute the shortest paths from the target node (n-1) to all other nodes by reversing the graph edges. Use these two results to determine if an edge can be part of any shortest path.

This function constructs the graph and uses Dijkstra's algorithm twice to gather the shortest path weights from the start to all nodes and from the end to all nodes (by reversing the graph). It checks if for each edge (u, v), the sum of the shortest path from the start to u, the weight w of the edge, and the shortest path from v to the end equals the shortest path from start to end. If so, the edge is part of at least one shortest path.

Code

PythonC++JavaJavaScript

Python

C++

Java

JavaScript

Complexity

Time Complexity: O((n + m) log n), as Dijkstra's algorithm, is run twice, and each involving operations on vertices and edges.

Space Complexity: O(n + m), for storing the graphs and distance arrays.

Try this approach in the editor →

Approach 2: Approach 2: Bellman-Ford Algorithm with Inverse Relaxation

This approach employs the Bellman-Ford algorithm to find the shortest paths. After determining the shortest paths from the start, we use another Bellman-Ford process but in reverse, allowing edge relaxation from the end node. This method checks if an edge contributes as a segment to any shortest paths.

The Bellman-Ford algorithm is applied twice: once for the original edges to determine distances from the starting node, and once on reversed edges for distances to the end node. It checks edge validity in shortest paths through summation of these measurements compared to the overall shortest path distance.

Code

PythonC++JavaJavaScript

Python

C++

Java

JavaScript

Complexity

Time Complexity: O(n * m), as Bellman-Ford is applied twice with edge relaxation.

Space Complexity: O(n), maintaining distance arrays primarily.

Try this approach in the editor →

Approach 3: 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.

Then, we use the Dijkstra algorithm to calculate the shortest distance from node 0 to other nodes. The specific steps are as follows:

  1. Create a priority queue q to store the distance and node number of the nodes. Initially, add node 0 to the queue with a distance of 0.
  2. Take a node a from the queue. If the distance da of a is greater than dist[a], it means that a has been updated, so skip it directly.
  3. Traverse all neighbor nodes b of node a. If dist[b] > dist[a] + w, update dist[b] = dist[a] + w, and add node b to the queue.
  4. Repeat steps 2 and 3 until the queue is empty.

Next, we create an answer array ans of length m, initially all elements are false. If dist[n - 1] is infinity, it means that node 0 cannot reach node n - 1, return ans directly. Otherwise, we start from node n - 1, traverse all edges, if the edge (a, b, i) satisfies dist[a] = dist[b] + w, set ans[i] to true, and add node b to the queue.

Finally, return the answer.

The time complexity is O(m times log m), and the space complexity is O(n + m), where n and m are the number of nodes and edges respectively.

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Double Dijkstra's Algorithm

Time Complexity: O((n + m) log n), as Dijkstra's algorithm, is run twice, and each involving operations on vertices and edges.

Space Complexity: O(n + m), for storing the graphs and distance arrays.

Approach 2: Bellman-Ford Algorithm with Inverse Relaxation

Time Complexity: O(n * m), as Bellman-Ford is applied twice with edge relaxation.

Space Complexity: O(n), maintaining distance arrays primarily.

Heap Optimized Dijkstra—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Double Dijkstra's AlgorithmO(E log V)O(V + E)Best general solution for weighted graphs with non-negative edges
Bellman-Ford with Inverse RelaxationO(V * E)O(V + E)Useful when negative edge weights are possible or when demonstrating relaxation-based shortest paths

Video Solution

Find Edges in Shortest Paths | Dijkstra's Algo | Full Intuition | Leetcode 3123 | codestorywithMIK • codestorywithMIK • 6,270 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Find Edges in Shortest Paths easy or hard?
Find Edges in Shortest Paths is classified as a Hard problem on LeetCode. It requires combining two shortest-path computations and reasoning about how edges contribute to optimal paths, which is more advanced than standard Dijkstra questions.
Find Edges in Shortest Paths Python or Java solution?
Python and Java implementations typically build an adjacency list, run Dijkstra twice using a priority queue, and then check each edge against the shortest path equation. Python uses heapq for the min-heap, while Java commonly uses PriorityQueue.
How to solve Find Edges in Shortest Paths in O(E log V)?
Run Dijkstra from node 0 to compute distStart and from node n-1 to compute distEnd. Calculate the shortest distance from 0 to n-1. For every edge (u, v, w), check whether distStart[u] + w + distEnd[v] equals the shortest distance or the symmetric condition for the reverse direction. If true, the edge belongs to a shortest path.
What is the best approach for Find Edges in Shortest Paths?
Double Dijkstra's Algorithm is the most efficient and commonly expected approach. Run Dijkstra from the source and from the destination to compute prefix and suffix distances. An edge is part of a shortest path if distStart[u] + w + distEnd[v] equals the shortest distance to the target. The total complexity is O(E log V).
What data structure is used in Find Edges in Shortest Paths?
The main data structure is a min-heap (priority queue) used by Dijkstra's algorithm to always expand the node with the smallest tentative distance. The graph is stored using adjacency lists, and arrays track shortest distances from both source and destination.
What is the time complexity of Find Edges in Shortest Paths?
The optimal solution using Double Dijkstra runs in O(E log V) time because Dijkstra's algorithm processes each edge using a priority queue. Space complexity is O(V + E) for storing adjacency lists and distance arrays. The Bellman-Ford alternative runs in O(V * E) time.
Is Find Edges in Shortest Paths asked at Google, Amazon, or Meta?
Variants of this problem appear in interviews at companies that test advanced graph algorithms, including Google and Meta. The question evaluates understanding of shortest path decomposition, Dijkstra's algorithm, and graph traversal techniques.

Ready to solve this problem?

Practice Find Edges in Shortest Paths with our built-in code editor and test cases.

Practice on FleetCode
Previous

Binary Tree Inorder Traversal

Next

Validate Binary Search Tree