# Find Edges in Shortest Paths
**Difficulty:** HARD
[External](https://leetcode.com/problems/find-edges-in-shortest-paths)
Canonical: https://scaleengineer.com/dsa/problems/find-edges-in-shortest-paths
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search), [Shortest Path](https://scaleengineer.com/algorithms/shortest-path)
**Data structures:** Heap (Priority Queue), Graph
**Companies:** [WeRide](https://scaleengineer.com/companies/weride)
---
## 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] = [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:**

![](https://assets.glich.co/dsa/find-edges-in-shortest-paths/image0.png) 

**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:**

![](https://assets.glich.co/dsa/find-edges-in-shortest-paths/image1.png) 

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

# Approaches
## Brute-Force Path Enumeration
This approach involves finding all possible simple paths from node 0 to node `n-1`. For each path, we calculate its total weight. We identify the minimum weight among all these paths, which is the shortest path distance. Finally, we iterate through all the edges and check if an edge is part of any path whose total weight equals the shortest path distance.
**Time:** O(P * N), where P is the number of simple paths. The number of paths can be exponential or even factorial in the number of nodes, making this approach infeasible for anything but very small graphs. · **Space:** O(P * N), where P is the number of simple paths and N is the number of nodes. In the worst case, P can be as large as O(N!), making the space complexity enormous.
**Pros:** Conceptually simple and easy to understand.
**Cons:** Extremely inefficient and will time out on the given constraints.; The number of simple paths in a graph can be exponential, leading to prohibitive time and memory usage.
### Explanation
The most straightforward, yet impractical, way to solve this problem is to enumerate every possible path from the start node (0) to the end node (`n-1`). This can be achieved using a backtracking algorithm, typically a variation of Depth First Search (DFS), that explores all routes without visiting the same node twice within a single path.

As each path is discovered, its total weight is computed by summing the weights of its constituent edges. These paths and their weights are stored. After the search is complete, we find the minimum weight among all paths, which represents the length of the shortest path. 

With the shortest path length known, we can then determine which edges belong to a shortest path. We iterate through our original list of edges. For each edge, we check if it is included in any of the paths we found that have a total weight equal to the minimum shortest path length. If it is, we mark its corresponding entry in the final answer array as `true`.
### Algorithm
- Use a recursive Depth First Search (DFS) to find all simple paths from node 0 to node `n-1`.
- Store each path and its calculated total weight.
- After finding all paths, determine the minimum weight, `shortest_dist`, among them.
- Initialize a boolean array `answer` of size `m` to all `false`.
- Iterate through each edge `edges[i]`. For this edge, iterate through all the found paths.
- If a path's weight is equal to `shortest_dist` and it contains `edges[i]`, set `answer[i]` to `true` and move to the next edge.

## Per-Edge Shortest Path Calculation
This approach improves upon brute force by using the properties of shortest paths. First, we calculate the global shortest path distance from node 0 to `n-1`. Then, for each edge `(u, v)` with weight `w`, we check if it can be part of a shortest path. The condition for this is that the shortest path from 0 to `u`, plus the edge weight `w`, plus the shortest path from `v` to `n-1`, must equal the global shortest path distance. This check is performed for every single edge.
**Time:** O(m * (m log n)). A single Dijkstra's run is O(m log n). This is repeated for many of the `m` edges, leading to a prohibitive total time complexity. · **Space:** O(m + n) for the adjacency list and distance arrays.
**Pros:** More efficient than brute-force path enumeration.; Correctly applies the mathematical properties of shortest paths.
**Cons:** Very high time complexity due to running Dijkstra's algorithm repeatedly.; Will result in a 'Time Limit Exceeded' error for the given problem constraints.
### Explanation
A more refined method involves using the defining property of an edge on a shortest path. An edge `(u, v)` with weight `w` lies on a shortest path from source `s` to target `t` if `dist(s, u) + w + dist(v, t) = dist(s, t)`.

First, we perform one run of Dijkstra's algorithm starting from node 0 to find the shortest distance from 0 to all other nodes, `dist(0, x)`. This gives us the overall shortest path length, `dist(0, n-1)`, and the first term, `dist(0, u)`, for our check.

Then, we iterate through each edge `(u, v)` in the graph. For each edge, we need to verify the condition. We already have `dist(0, u)`. To get `dist(v, n-1)`, we would need to run another SSSP algorithm, like Dijkstra's, starting from node `v`. Since we have to do this for every edge, this approach requires running Dijkstra's algorithm `m+1` times in total (one initial run, and one for each of the `m` edges). This is computationally expensive.
### Algorithm
- Build an adjacency list representation of the graph.
- Run Dijkstra's algorithm from source 0 to compute `dist(0, x)` for all nodes `x`. Store these in an array `dist0`.
- The overall shortest path length is `shortest_path_len = dist0[n-1]`.
- If `n-1` is unreachable, all answers are `false`.
- Initialize a boolean array `answer` of size `m` to `false`.
- Iterate through each edge `edges[i] = (u, v, w)`:
  - To check the condition `dist(0, u) + w + dist(v, n-1) == shortest_path_len`, we need `dist(v, n-1)`. 
  - Run a full Dijkstra's algorithm starting from node `v` to find `dist(v, n-1)`.
  - If the condition holds, set `answer[i] = true`.
  - Also check the other direction: `dist(0, v) + w + dist(u, n-1) == shortest_path_len`, which requires another Dijkstra run from `u`.

## Two-Pass Dijkstra's Algorithm
This is the most efficient approach. It leverages the property that an edge `(u, v)` with weight `w` is on a shortest path from a source `s` to a destination `t` if and only if `dist(s, u) + w + dist(v, t) = dist(s, t)`. Instead of recalculating distances for each edge, we can pre-calculate all necessary distances in just two runs of Dijkstra's algorithm: one from the source and one from the destination.
**Time:** O(m log n). Building the graph is O(m+n). Each of the two Dijkstra runs takes O((m+n) log n), which simplifies to O(m log n) as `m` is typically at least `n-1`. The final loop over edges is O(m). The bottleneck is the two Dijkstra calls. · **Space:** O(m + n). This is for the adjacency list (O(m+n)), two distance arrays (O(n)), and the priority queue used in Dijkstra's algorithm (O(n)).
**Pros:** Optimal time complexity for this problem.; Efficiently computes all necessary distances with just two SSSP runs.; Scales well for large graphs within the given constraints.
**Cons:** Slightly more complex to implement than a single Dijkstra run.; Requires careful handling of large path weights to avoid integer overflow, by using 64-bit integers (long) for distances.
### Explanation
The optimal solution is based on the same shortest path property but avoids redundant computations. We need two pieces of information for each node `x`: the shortest distance from the start node 0 to `x`, and the shortest distance from `x` to the end node `n-1`.

We can compute all `dist(0, x)` values with a single run of Dijkstra's algorithm starting from node 0.

To compute all `dist(x, n-1)` values, we can run Dijkstra's algorithm starting from node `n-1`. Since the graph is undirected, the shortest distance from `x` to `n-1` is the same as from `n-1` to `x`. So, this second Dijkstra run gives us all the `dist(n-1, x)` values we need.

After these two runs, we have the overall shortest path length `dist(0, n-1)`. If this distance is infinity, no path exists, so all edges are not on a shortest path.

Otherwise, we can iterate through every edge `(u, v)` with weight `w` just once. For each edge, we check if `dist(0, u) + w + dist(n-1, v) == dist(0, n-1)`. Because the edge is undirected, we must also check the path through `v` first: `dist(0, v) + w + dist(n-1, u) == dist(0, n-1)`. If either of these conditions is met, the edge is part of at least one shortest path, and we mark it as `true` in our answer array.

This approach requires only two SSSP computations, making it highly efficient.
```java
class Solution {
    public boolean[] findAnswer(int n, int[][] edges) {
        List<List<int[]>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }
        for (int[] edge : edges) {
            adj.get(edge[0]).add(new int[]{edge[1], edge[2]});
            adj.get(edge[1]).add(new int[]{edge[0], edge[2]});
        }

        long[] distFrom0 = dijkstra(0, n, adj);
        long[] distFromN1 = dijkstra(n - 1, n, adj);

        long shortestPathLen = distFrom0[n - 1];
        boolean[] answer = new boolean[edges.length];

        if (shortestPathLen == Long.MAX_VALUE) {
            return answer; // All false if no path exists
        }

        for (int i = 0; i < edges.length; i++) {
            int u = edges[i][0];
            int v = edges[i][1];
            int w = edges[i][2];

            if (distFrom0[u] != Long.MAX_VALUE && distFromN1[v] != Long.MAX_VALUE &&
                distFrom0[u] + w + distFromN1[v] == shortestPathLen) {
                answer[i] = true;
            }
            
            if (distFrom0[v] != Long.MAX_VALUE && distFromN1[u] != Long.MAX_VALUE &&
                distFrom0[v] + w + distFromN1[u] == shortestPathLen) {
                answer[i] = true;
            }
        }

        return answer;
    }

    private long[] dijkstra(int startNode, int n, List<List<int[]>> adj) {
        long[] dist = new long[n];
        Arrays.fill(dist, Long.MAX_VALUE);
        dist[startNode] = 0;

        // PriorityQueue stores {distance, node}
        PriorityQueue<long[]> pq = new PriorityQueue<>((a, b) -> Long.compare(a[0], b[0]));
        pq.offer(new long[]{0, startNode});

        while (!pq.isEmpty()) {
            long[] current = pq.poll();
            long d = current[0];
            int u = (int) current[1];

            if (d > dist[u]) {
                continue;
            }

            for (int[] edge : adj.get(u)) {
                int v = edge[0];
                int weight = edge[1];
                if (dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight;
                    pq.offer(new long[]{dist[v], v});
                }
            }
        }
        return dist;
    }
}
```
### Algorithm
- Build an adjacency list for the graph.
- Create two distance arrays, `dist_from_0` and `dist_from_n_1`, of size `n`, initialized to infinity.
- Run Dijkstra's algorithm starting from node 0 to populate `dist_from_0`. Set `dist_from_0[0] = 0` initially.
- Run Dijkstra's algorithm starting from node `n-1` to populate `dist_from_n_1`. Set `dist_from_n_1[n-1] = 0` initially.
- Get the shortest path length: `shortest_path_len = dist_from_0[n-1]`.
- If `shortest_path_len` is infinity, `n-1` is unreachable. Return an array of `m` `false` values.
- Create a boolean array `answer` of size `m`.
- Iterate through each edge `edges[i] = (u, v, w)`:
  - Check if `dist_from_0[u] + w + dist_from_n_1[v] == shortest_path_len`.
  - Also check if `dist_from_0[v] + w + dist_from_n_1[u] == shortest_path_len`.
  - If either condition is true, set `answer[i] = true`.
- Return the `answer` array.

# Solutions
### Java

```java
class Solution {
public
  boolean[] findAnswer(int n, int[][] edges) {
    List<int[]>[] g = new List[n];
    Arrays.setAll(g, k->new ArrayList<>());
    int m = edges.length;
    for (int i = 0; i < m; ++i) {
      int a = edges[i][0], b = edges[i][1], w = edges[i][2];
      g[a].add(new int[]{b, w, i});
      g[b].add(new int[]{a, w, i});
    }
    int[] dist = new int[n];
    final int inf = 1 << 30;
    Arrays.fill(dist, inf);
    dist[0] = 0;
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b)->a[0] - b[0]);
    pq.offer(new int[]{0, 0});
    while (!pq.isEmpty()) {
      var p = pq.poll();
      int da = p[0], a = p[1];
      if (da > dist[a]) {
        continue;
      }
      for (var e : g[a]) {
        int b = e[0], w = e[1];
        if (dist[b] > dist[a] + w) {
          dist[b] = dist[a] + w;
          pq.offer(new int[]{dist[b], b});
        }
      }
    }
    boolean[] ans = new boolean[m];
    if (dist[n - 1] == inf) {
      return ans;
    }
    Deque<Integer> q = new ArrayDeque<>();
    q.offer(n - 1);
    while (!q.isEmpty()) {
      int a = q.poll();
      for (var e : g[a]) {
        int b = e[0], w = e[1], i = e[2];
        if (dist[a] == dist[b] + w) {
          ans[i] = true;
          q.offer(b);
        }
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution { public: vector < bool > findAnswer ( int n , vector < vector < int >>& edges ) { vector < vector < array < int , 3 >>> g ( n ); int m = edges . size (); for ( int i = 0 ; i < m ; ++ i ) { auto e = edges [ i ]; int a = e [ 0 ], b = e [ 1 ], w = e [ 2 ]; g [ a ]. push_back ({ b , w , i }); g [ b ]. push_back ({ a , w , i }); } const int inf = 1 << 30 ; vector < int > dist ( n , inf ); dist [ 0 ] = 0 ; using pii = pair < int , int > ; priority_queue < pii , vector < pii > , greater < pii >> pq ; pq . push ({ 0 , 0 }); while ( ! pq . empty ()) { auto [ da , a ] = pq . top (); pq . pop (); if ( da > dist [ a ]) { continue ; } for ( auto [ b , w , _ ] : g [ a ]) { if ( dist [ b ] > dist [ a ] + w ) { dist [ b ] = dist [ a ] + w ; pq . push ({ dist [ b ], b }); } } } vector < bool > ans ( m ); if ( dist [ n - 1 ] == inf ) { return ans ; } queue < int > q { { n - 1 } }; while ( ! q . empty ()) { int a = q . front (); q . pop (); for ( auto [ b , w , i ] : g [ a ]) { if ( dist [ a ] == dist [ b ] + w ) { ans [ i ] = true ; q . push ( b ); } } } return ans ; } };
```

### Python

```python
class Solution:
    def findAnswer(self, n: int, edges: List[List[int]]) -> List[bool]: g = defaultdict(list) for i, (a, b, w) in enumerate(edges): g[a]. append((b, w, i)) g[b]. append((a, w, i)) dist = [inf] * n dist[0] = 0 q = [(0, 0)] while q: da, a = heappop(q) if da > dist[a]: continue for b, w, _ in g[a]: if dist[b] > dist[a] + w: dist[b] = dist[a] + w heappush(q, (dist[b], b)) m = len(edges) ans = [False] * m if dist[n - 1] == inf: return ans q = deque([n - 1]) while q: a = q . popleft() for b, w, i in g[a]: if dist[a] == dist[b] + w: ans[i] = True q . append(b) return ans

```