Practice/Google/Leetcode 3123. Find Edges in Shortest Paths

Leetcode 3123. Find Edges in Shortest Paths

CodingOptional

Problem

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

Your task is to determine, for each edge in the input array, whether that edge lies on at least one shortest path from node 0 to node n-1. Return a boolean array where the i-th element is true if the i-th edge is part of at least one shortest path, and false otherwise.

An edge is considered to be on a shortest path if using that edge in a path from node 0 to node n-1 results in a path with length equal to the minimum possible distance between these two nodes.

Requirements

1. Compute the shortest distance from node 0 to node n-1
2. For each edge, determine if it can be part of any shortest path
3. Return results in the same order as the input edges array
4. Handle graphs where multiple shortest paths may exist
5. The graph is guaranteed to be connected

Constraints

• 2 ≤ n ≤ 1000
• 1 ≤ edges.length ≤ min(5000, n * (n-1) / 2)
• edges[i].length == 3
• 0 ≤ ui, vi < n
• ui ≠ vi
• 1 ≤ wi ≤ 10^6
• There are no duplicate edges
• The graph is connected
• Expected time complexity: O(E * log V) where E is the number of edges and V is the number of vertices

Examples

Example 1:

Input: n = 4, edges = [[0,1,1],[1,2,1],[2,3,1],[0,3,4]] Output: [true,true,true,false] Explanation: The shortest path from 0 to 3 has length 3 using the route 0->1->2->3. The first three edges are all part of this shortest path, but the direct edge from 0 to 3 with weight 4 is not on any shortest path.

Example 2:

Input: n = 4, edges = [[0,1,1],[1,3,1],[0,2,1],[2,3,1]] Output: [true,true,true,true] Explanation: The shortest distance from 0 to 3 is 2. There are two shortest paths: 0->1->3 and 0->2->3. All four edges participate in at least one of these paths.

Example 3:

Input: n = 3, edges = [[0,1,1],[1,2,1],[0,2,5]] Output: [true,true,false] Explanation: The shortest path is 0->1->2 with length 2. The edge from 0 to 2 with weight 5 is longer than the shortest path and thus not critical.