Find Edges in Shortest Paths

Find Edges in Shortest Paths

What is this problem about?

The Find Edges in Shortest Paths interview question is a high-level graph problem. You are given a weighted, undirected graph with n nodes and a list of edges. Your goal is to find all the edges that belong to at least one shortest path between a starting node (usually node 0) and a target node (usually node n-1). You need to return a boolean array where each entry indicates if the corresponding edge is part of a shortest path.

Why is this asked in interviews?

This Find Edges in Shortest Paths coding problem is used by firms like DoorDash to assess a candidate's mastery of graph theory and pathfinding optimizations. It requires more than just finding one shortest path; it requires understanding the mathematical relationship between distances. It tests your ability to apply Dijkstra's algorithm effectively and reason about edge weights in a complex network.

Algorithmic pattern used

This problem follows the Shortest Path, Graph, Heap (Priority Queue) interview pattern. The core insight is that an edge (u, v) with weight w is part of a shortest path from S to T if: Dist(S, u) + w + Dist(v, T) == TotalShortestDist or Dist(S, v) + w + Dist(u, T) == TotalShortestDist. To solve this, you run Dijkstra twice: once starting from S and once starting from T.

Example explanation

Suppose we have nodes 0, 1, 2 and edges:

• (0, 1) weight 1
• (1, 2) weight 2
• (0, 2) weight 3 Shortest distance from 0 to 2 is 3.

1. Running Dijkstra from 0: dist0[0]=0, dist0[1]=1, dist0[2]=3.
2. Running Dijkstra from 2: dist2[2]=0, dist2[1]=2, dist2[0]=3.
3. Check edge (0, 1): dist0[0] + 1 + dist2[1] = 0 + 1 + 2 = 3. Match! This edge is part of a shortest path.
4. Check edge (1, 2): dist0[1] + 2 + dist2[2] = 1 + 2 + 0 = 3. Match! This edge is also part of a shortest path.
5. Check edge (0, 2): dist0[0] + 3 + dist2[2] = 0 + 3 + 0 = 3. Match! This direct edge is also a shortest path.

Common mistakes candidates make

• Single Dijkstra Attempt: Trying to track parents during a single Dijkstra run. This is difficult because one edge can lead to multiple shortest paths.
• Integer Overflow: Forgetting that edge weights can be large and failing to use long integers for distances.
• Ignoring the Second Dijkstra: Not realizing that knowing the distance from the end node to all other nodes is the most efficient way to validate edges.

Interview preparation tip

For path problems involving "all shortest paths," always consider running your algorithm from both directions (source-to-all and destination-to-all). This "meet-in-the-middle" logic often simplifies path validation from O(E) complexity down to a simple O(1) check per edge.