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:
0 -> 1 -> 5: The sum of weights is 4 + 1 = 5.0 -> 2 -> 3 -> 5: The sum of weights is 1 + 1 + 3 = 5.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 * 104m == edges.length1 <= m <= min(5 * 104, n * (n - 1) / 2)0 <= ai, bi < nai != bi1 <= wi <= 105This 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.
C++
Java
JavaScript
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.
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.
C++
Java
JavaScript
Time Complexity: O(n * m), as Bellman-Ford is applied twice with edge relaxation.
Space Complexity: O(n), maintaining distance arrays primarily.
| 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. |
Unique Paths - Dynamic Programming - Leetcode 62 • NeetCode • 157,703 views views
Watch 9 more video solutions →Practice Find Edges in Shortest Paths with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor