3123. Find Edges in Shortest Paths - Solution

The problem

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] = [a_i, b_i, w_i] indicates that there is an edge between nodes a_i and b_i with weight w_i.

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 * 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⁵
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.

Python

import heapq

def dijkstra(n, graph, start):
    dist = [float('inf')] * n
    dist[start] = 0
    heap = [(0, start)]
    while heap:
        d, node = heapq.heappop(heap)
        if d > dist[node]:
            continue
        for nei, w in graph[node]:
            if dist[node] + w < dist[nei]:
                dist[nei] = dist[node] + w
                heapq.heappush(heap, (dist[nei], nei))
    return dist

def find_shortest_path_edges(n, edges):
    graph = [[] for _ in range(n)]
    for u, v, w in edges:
        graph[u].append((v, w))
        graph[v].append((u, w))
    
    dist_from_start = dijkstra(n, graph, 0)
    reverse_graph = [[] for _ in range(n)]
    for u, v, w in edges:
        reverse_graph[v].append((u, w))
        reverse_graph[u].append((v, w))
    dist_from_end = dijkstra(n, reverse_graph, n - 1)
    shortest = dist_from_start[n - 1]

    answer = [False] * len(edges)
    for i, (u, v, w) in enumerate(edges):
        if dist_from_start[u] + w + dist_from_end[v] == shortest or dist_from_start[v] + w + dist_from_end[u] == shortest:
            answer[i] = True
    return answer

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]]
print(find_shortest_path_edges(n, edges))

Java

import java.util.*;

class Solution {
    private static int[] dijkstra(int n, List<List<int[]>> graph, int start) {
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[start] = 0;
        PriorityQueue<int[]> heap = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
        heap.offer(new int[]{0, start});

        while (!heap.isEmpty()) {
            int[] curr = heap.poll();
            int d = curr[0], node = curr[1];
            if (d > dist[node]) continue;
            
            for (int[] neighbor : graph.get(node)) {
                int nei = neighbor[0], w = neighbor[1];
                if (dist[node] + w < dist[nei]) {
                    dist[nei] = dist[node] + w;
                    heap.offer(new int[]{dist[nei], nei});
                }
            }
        }
        return dist;
    }

    public static boolean[] find_shortest_path_edges(int n, int[][] edges) {
        List<List<int[]>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
        for (int[] edge : edges) {
            int u = edge[0], v = edge[1], w = edge[2];
            graph.get(u).add(new int[]{v, w});
            graph.get(v).add(new int[]{u, w});
        }
        
        int[] distFromStart = dijkstra(n, graph, 0);
        List<List<int[]>> reverseGraph = new ArrayList<>();
        for (int i = 0; i < n; i++) reverseGraph.add(new ArrayList<>());
        for (int[] edge : edges) {
            int u = edge[0], v = edge[1], w = edge[2];
            reverseGraph.get(v).add(new int[]{u, w});
            reverseGraph.get(u).add(new int[]{v, w});
        }
        int[] distFromEnd = dijkstra(n, reverseGraph, n - 1);
        int shortest = distFromStart[n - 1];

        boolean[] answer = new boolean[edges.length];
        for (int i = 0; i < edges.length; i++) {
            int u = edges[i][0], v = edges[i][1], w = edges[i][2];
            if (distFromStart[u] + w + distFromEnd[v] == shortest ||
                distFromStart[v] + w + distFromEnd[u] == shortest) {
                answer[i] = true;
            }
        }
        return answer;
    }

    public static void main(String[] args) {
        int n = 6;
        int[][] 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}};
        boolean[] answer = find_shortest_path_edges(n, edges);
        System.out.println(Arrays.toString(answer));
    }
}

C++

#include <iostream>
#include <vector>
#include <queue>
#include <utility>

using namespace std;

vector<int> dijkstra(int n, vector<vector<pair<int, int>>>& graph, int start) {
    vector<int> dist(n, INT_MAX);
    dist[start] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> heap;
    heap.emplace(0, start);
    while (!heap.empty()) {
        auto [d, node] = heap.top(); heap.pop();
        if (d > dist[node]) continue;
        
        for (auto& [nei, w] : graph[node]) {
            if (dist[node] + w < dist[nei]) {
                dist[nei] = dist[node] + w;
                heap.emplace(dist[nei], nei);
            }
        }
    }
    return dist;
}

vector<bool> find_shortest_path_edges(int n, vector<vector<int>>& edges) {
    vector<vector<pair<int, int>>> graph(n);
    for (auto& e : edges) {
        int u = e[0], v = e[1], w = e[2];
        graph[u].emplace_back(v, w);
        graph[v].emplace_back(u, w);
    }
    
    vector<int> dist_from_start = dijkstra(n, graph, 0);
    vector<vector<pair<int, int>>> reverse_graph(n);
    for (auto& e : edges) {
        int u = e[0], v = e[1], w = e[2];
        reverse_graph[v].emplace_back(u, w);
        reverse_graph[u].emplace_back(v, w);
    }
    vector<int> dist_from_end = dijkstra(n, reverse_graph, n - 1);
    int shortest = dist_from_start[n - 1];

    vector<bool> answer(edges.size(), false);
    for (size_t i = 0; i < edges.size(); ++i) {
        int u = edges[i][0], v = edges[i][1], w = edges[i][2];
        if (dist_from_start[u] + w + dist_from_end[v] == shortest ||
            dist_from_start[v] + w + dist_from_end[u] == shortest) {
            answer[i] = true;
        }
    }
    return answer;
}

int main() {
    int n = 6;
    vector<vector<int>> 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}};
    vector<bool> answer = find_shortest_path_edges(n, edges);
    for (bool a : answer) {
        cout << (a ? "true" : "false") << " ";
    }
    cout << endl;
    return 0;
}

JavaScript

function dijkstra(n, graph, start) {
    let dist = Array(n).fill(Infinity);
    dist[start] = 0;
    let pq = new MinPriorityQueue({ priority: x => x[0] });
    pq.enqueue([0, start]);

    while (!pq.isEmpty()) {
        let [d, node] = pq.dequeue().element;
        if (d > dist[node]) continue;

        for (let [nei, w] of graph[node]) {
            if (dist[node] + w < dist[nei]) {
                dist[nei] = dist[node] + w;
                pq.enqueue([dist[nei], nei]);
            }
        }
    }
    return dist;
}

function findShortestPathEdges(n, edges) {
    let graph = Array.from({ length: n }, () => []);
    for (let [u, v, w] of edges) {
        graph[u].push([v, w]);
        graph[v].push([u, w]);
    }

    let distFromStart = dijkstra(n, graph, 0);
    let reverseGraph = Array.from({ length: n }, () => []);
    for (let [u, v, w] of edges) {
        reverseGraph[v].push([u, w]);
        reverseGraph[u].push([v, w]);
    }
    let distFromEnd = dijkstra(n, reverseGraph, n - 1);
    let shortest = distFromStart[n - 1];

    let answer = new Array(edges.length).fill(false);
    for (let i = 0; i < edges.length; i++) {
        let [u, v, w] = edges[i];
        if (distFromStart[u] + w + distFromEnd[v] === shortest ||
            distFromStart[v] + w + distFromEnd[u] === shortest) {
            answer[i] = true;
        }
    }
    return answer;
}

let n = 6;
let 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]];
console.log(findShortestPathEdges(n, edges));

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.

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.

Python

def bellman_ford(n, edges, start):
    dist = [float('inf')] * n
    dist[start] = 0
    for _ in range(n - 1):
        for u, v, w in edges:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    return dist


def find_shortest_path_edges(n, edges):
    forward_dist = bellman_ford(n, edges, 0)
    reverse_edges = [[v, u, w] for u, v, w in edges]
    backward_dist = bellman_ford(n, reverse_edges, n - 1)
    shortest = forward_dist[n - 1]
    answer = [False] * len(edges)
    for i, (u, v, w) in enumerate(edges):
        if (forward_dist[u] != float('inf') and forward_dist[u] + w + backward_dist[v] == shortest) or \
           (forward_dist[v] != float('inf') and forward_dist[v] + w + backward_dist[u] == shortest):
            answer[i] = True
    return answer

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]]
print(find_shortest_path_edges(n, edges))

Java

import java.util.*;

class SolutionBF {
    private static int[] bellmanFord(int n, int[][] edges, int start) {
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[start] = 0;

        for (int i = 0; i < n - 1; i++) {
            for (int[] edge : edges) {
                int u = edge[0], v = edge[1], w = edge[2];
                if (dist[u] != Integer.MAX_VALUE && dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                }
            }
        }
        return dist;
    }

    public static boolean[] findShortestPathEdges(int n, int[][] edges) {
        int[] forwardDist = bellmanFord(n, edges, 0);
        int[][] reverseEdges = new int[edges.length][3];
        for (int i = 0; i < edges.length; i++) {
            reverseEdges[i][0] = edges[i][1];
            reverseEdges[i][1] = edges[i][0];
            reverseEdges[i][2] = edges[i][2];
        }
        int[] backwardDist = bellmanFord(n, reverseEdges, n - 1);
        int shortest = forwardDist[n - 1];
        boolean[] answer = new boolean[edges.length];
        
        for (int i = 0; i < edges.length; i++) {
            int u = edges[i][0], v = edges[i][1], w = edges[i][2];
            if ((forwardDist[u] != Integer.MAX_VALUE && forwardDist[u] + w + backwardDist[v] == shortest) ||
                (forwardDist[v] != Integer.MAX_VALUE && forwardDist[v] + w + backwardDist[u] == shortest)) {
                answer[i] = true;
            }
        }

        return answer;
    }

    public static void main(String[] args) {
        int n = 6;
        int[][] 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}};
        boolean[] answer = findShortestPathEdges(n, edges);
        System.out.println(Arrays.toString(answer));
    }
}

C++

#include <iostream>
#include <vector>
#include <climits>

using namespace std;

vector<int> bellman_ford(int n, const vector<vector<int>>& edges, int start) {
    vector<int> dist(n, INT_MAX);
    dist[start] = 0;
    for (int i = 0; i < n - 1; ++i) {
        for (const auto& edge : edges) {
            int u = edge[0], v = edge[1], w = edge[2];
            if (dist[u] != INT_MAX && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
            }
        }
    }
    return dist;
}

vector<bool> find_shortest_path_edges(int n, vector<vector<int>>& edges) {
    vector<int> forwardDist = bellman_ford(n, edges, 0);
    vector<vector<int>> reverseEdges;
    for (const auto& edge : edges) {
        reverseEdges.push_back({edge[1], edge[0], edge[2]});
    }
    vector<int> backwardDist = bellman_ford(n, reverseEdges, n - 1);
    int shortest = forwardDist[n - 1];

    vector<bool> answer(edges.size(), false);
    for (size_t i = 0; i < edges.size(); ++i) {
        int u = edges[i][0], v = edges[i][1], w = edges[i][2];
        if ((forwardDist[u] != INT_MAX && forwardDist[u] + w + backwardDist[v] == shortest) ||
            (forwardDist[v] != INT_MAX && forwardDist[v] + w + backwardDist[u] == shortest)) {
            answer[i] = true;
        }
    }
    return answer;
}

int main() {
    int n = 6;
    vector<vector<int>> 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}};
    vector<bool> answer = find_shortest_path_edges(n, edges);
    for (bool val : answer) {
        cout << (val ? "true" : "false") << ' ';
    }
    cout << endl;
    return 0;
}

JavaScript

function bellmanFord(n, edges, start) {
    let dist = new Array(n).fill(Infinity);
    dist[start] = 0;
    for (let i = 0; i < n - 1; i++) {
        for (let [u, v, w] of edges) {
            if (dist[u] !== Infinity && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
            }
        }
    }
    return dist;
}

function findShortestPathEdges(n, edges) {
    let forwardDist = bellmanFord(n, edges, 0);
    let reverseEdges = edges.map(([u, v, w]) => [v, u, w]);
    let backwardDist = bellmanFord(n, reverseEdges, n - 1);
    let shortest = forwardDist[n - 1];
    let answer = new Array(edges.length).fill(false);

    for (let i = 0; i < edges.length; i++) {
        let [u, v, w] = edges[i];
        if (forwardDist[u] !== Infinity && forwardDist[u] + w + backwardDist[v] === shortest ||
            forwardDist[v] !== Infinity && forwardDist[v] + w + backwardDist[u] === shortest) {
            answer[i] = true;
        }
    }
    return answer;
}

let n = 6;
let 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]];
console.log(findShortestPathEdges(n, edges));

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.

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:

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

func findAnswer(n int, edges [][]int) []bool {
	g := make([][][3]int, n)
	for i, e := range edges {
		a, b, w := e[0], e[1], e[2]
		g[a] = append(g[a], [3]int{b, w, i})
		g[b] = append(g[b], [3]int{a, w, i})
	}
	dist := make([]int, n)
	const inf int = 1 << 30
	for i := range dist {
		dist[i] = inf
	}
	dist[0] = 0
	pq := hp{{0, 0}}
	for len(pq) > 0 {
		p := heap.Pop(&pq).(pair)
		da, a := p.dis, p.u
		if da > dist[a] {
			continue
		}
		for _, e := range g[a] {
			b, w := e[0], e[1]
			if dist[b] > dist[a]+w {
				dist[b] = dist[a] + w
				heap.Push(&pq, pair{dist[b], b})
			}
		}
	}
	ans := make([]bool, len(edges))
	if dist[n-1] == inf {
		return ans
	}
	q := []int{n - 1}
	for len(q) > 0 {
		a := q[0]
		q = q[1:]
		for _, e := range g[a] {
			b, w, i := e[0], e[1], e[2]
			if dist[a] == dist[b]+w {
				ans[i] = true
				q = append(q, b)
			}
		}
	}
	return ans
}

type pair struct{ dis, u int }
type hp []pair

func (h hp) Len() int           { return len(h) }
func (h hp) Less(i, j int) bool { return h[i].dis < h[j].dis }
func (h hp) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(v any)        { *h = append(*h, v.(pair)) }
func (h *hp) Pop() any          { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }

Try this approach in the editor

Complexity comparison

Approach	Complexity
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	–

Approach

Complexity

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

–

Complexity analysis

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

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.

Find Edges in Shortest Paths solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Double Dijkstra's Algorithm

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

Approach 3: Heap Optimized Dijkstra

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Find Edges in Shortest Paths solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Double Dijkstra's Algorithm

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

Approach 3: Heap Optimized Dijkstra

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems