Find Edges in Shortest Paths

Problem

You are given an undirected weighted graph of n nodes numbered from 0 to `n

1. The graph consists of medges represented by a 2D arrayedges, where edges[i] = [ai, bi, wi]indicates that there is an edge between nodesaiandbiwith weightwi`.

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.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15



![](https://assets.leetcode.com/uploads/2024/03/05/graph35drawio-1.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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11



![](https://assets.leetcode.com/uploads/2024/03/05/graphhhh.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 * 10^4
m == edges.length
1 <= m <= min(5 * 104, n * (n - 1) / 2)
0 <= ai, bi < n
ai != bi
1 <= wi <= 10^5
There are no repeated edges.

Solution

Method 1 – Dijkstra + Path Backtracking 1

Intuition

To determine if an edge is part of any shortest path from node 0 to node n-1, we can use Dijkstra’s algorithm to find shortest distances, then check for each edge if it can be used in a shortest path by verifying if the sum of distances and edge weight equals the shortest path length.

Approach

Build the adjacency list from the edge list.
Run Dijkstra’s algorithm from node 0 to get the shortest distance to all nodes (dist_from_start).
Run Dijkstra’s algorithm from node n-1 to get the shortest distance to all nodes (dist_to_end).
The shortest path length from 0 to n-1 is dist_from_start[n-1].
For each edge [u, v, w], check if dist_from_start[u] + w + dist_to_end[v] == shortest or dist_from_start[v] + w + dist_to_end[u] == shortest. If so, mark answer[i] as true.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37


class Solution {
public:
    vector<bool> findAnswer(int n, vector<vector<int>>& edges) {
        vector<vector<pair<int,int>>> g(n);
        for (int i = 0; i < edges.size(); ++i) {
            int u = edges[i][0], v = edges[i][1], w = edges[i][2];
            g[u].push_back({v, w});
            g[v].push_back({u, w});
        }
        auto dijkstra = [&](int src) {
            vector<long long> d(n, 1e18);
            d[src] = 0;
            priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<>> pq;
            pq.push({0, src});
            while (!pq.empty()) {
                auto [du, u] = pq.top(); pq.pop();
                if (du > d[u]) continue;
                for (auto [v, w] : g[u]) {
                    if (d[v] > d[u] + w) {
                        d[v] = d[u] + w;
                        pq.push({d[v], v});
                    }
                }
            }
            return d;
        };
        auto d1 = dijkstra(0), d2 = dijkstra(n-1);
        long long shortest = d1[n-1];
        vector<bool> ans(edges.size());
        for (int i = 0; i < edges.size(); ++i) {
            int u = edges[i][0], v = edges[i][1], w = edges[i][2];
            if (d1[u] + w + d2[v] == shortest || d1[v] + w + d2[u] == shortest)
                ans[i] = true;
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40


func findAnswer(n int, edges [][]int) []bool {
    g := make([][][2]int, n)
    for i, e := range edges {
        u, v, w := e[0], e[1], e[2]
        g[u] = append(g[u], [2]int{v, w})
        g[v] = append(g[v], [2]int{u, w})
    }
    dijkstra := func(src int) []int {
        d := make([]int, n)
        for i := range d {
            d[i] = 1<<60
        }
        d[src] = 0
        pq := &heapInt{{0, src}}
        for pq.Len() > 0 {
            du, u := heap.Pop(pq).([2]int)[0], heap.Pop(pq).([2]int)[1]
            if du > d[u] {
                continue
            }
            for _, vw := range g[u] {
                v, w := vw[0], vw[1]
                if d[v] > d[u]+w {
                    d[v] = d[u]+w
                    heap.Push(pq, [2]int{d[v], v})
                }
            }
        }
        return d
    }
    d1, d2 := dijkstra(0), dijkstra(n-1)
    shortest := d1[n-1]
    ans := make([]bool, len(edges))
    for i, e := range edges {
        u, v, w := e[0], e[1], e[2]
        if d1[u]+w+d2[v] == shortest || d1[v]+w+d2[u] == shortest {
            ans[i] = true
        }
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39


class Solution {
    public List<Boolean> findAnswer(int n, int[][] edges) {
        List<int[]>[] g = new List[n];
        for (int i = 0; i < n; i++) g[i] = new ArrayList<>();
        for (int[] e : edges) {
            g[e[0]].add(new int[]{e[1], e[2]});
            g[e[1]].add(new int[]{e[0], e[2]});
        }
        long[] d1 = dijkstra(g, 0), d2 = dijkstra(g, n-1);
        long shortest = d1[n-1];
        List<Boolean> ans = new ArrayList<>();
        for (int[] e : edges) {
            int u = e[0], v = e[1], w = e[2];
            ans.add(d1[u]+w+d2[v]==shortest || d1[v]+w+d2[u]==shortest);
        }
        return ans;
    }
    private long[] dijkstra(List<int[]>[] g, int src) {
        int n = g.length;
        long[] d = new long[n];
        Arrays.fill(d, Long.MAX_VALUE);
        d[src] = 0;
        PriorityQueue<long[]> pq = new PriorityQueue<>(Comparator.comparingLong(a->a[0]));
        pq.add(new long[]{0, src});
        while (!pq.isEmpty()) {
            long[] top = pq.poll();
            long du = top[0]; int u = (int)top[1];
            if (du > d[u]) continue;
            for (int[] vw : g[u]) {
                int v = vw[0], w = vw[1];
                if (d[v] > d[u]+w) {
                    d[v] = d[u]+w;
                    pq.add(new long[]{d[v], v});
                }
            }
        }
        return d;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32


class Solution {
    fun findAnswer(n: Int, edges: Array<IntArray>): List<Boolean> {
        val g = Array(n) { mutableListOf<Pair<Int,Int>>() }
        for (e in edges) {
            g[e[0]].add(e[1] to e[2])
            g[e[1]].add(e[0] to e[2])
        }
        fun dijkstra(src: Int): LongArray {
            val d = LongArray(n) { Long.MAX_VALUE }
            d[src] = 0L
            val pq = java.util.PriorityQueue(compareBy<Pair<Long,Int>> { it.first })
            pq.add(0L to src)
            while (pq.isNotEmpty()) {
                val (du, u) = pq.poll()
                if (du > d[u]) continue
                for ((v, w) in g[u]) {
                    if (d[v] > d[u] + w) {
                        d[v] = d[u] + w
                        pq.add(d[v] to v)
                    }
                }
            }
            return d
        }
        val d1 = dijkstra(0)
        val d2 = dijkstra(n-1)
        val shortest = d1[n-1]
        return edges.map { (u, v, w) ->
            d1[u] + w + d2[v] == shortest || d1[v] + w + d2[u] == shortest
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


class Solution:
    def findAnswer(self, n: int, edges: list[list[int]]) -> list[bool]:
        from heapq import heappush, heappop
        g = [[] for _ in range(n)]
        for u, v, w in edges:
            g[u].append((v, w))
            g[v].append((u, w))
        def dijkstra(src: int) -> list[int]:
            d = [float('inf')] * n
            d[src] = 0
            pq = [(0, src)]
            while pq:
                du, u = heappop(pq)
                if du > d[u]: continue
                for v, w in g[u]:
                    if d[v] > d[u] + w:
                        d[v] = d[u] + w
                        heappush(pq, (d[v], v))
            return d
        d1 = dijkstra(0)
        d2 = dijkstra(n-1)
        shortest = d1[-1]
        ans = []
        for u, v, w in edges:
            ans.append(d1[u] + w + d2[v] == shortest or d1[v] + w + d2[u] == shortest)
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40


impl Solution {
    pub fn find_answer(n: i32, edges: Vec<Vec<i32>>) -> Vec<bool> {
        use std::collections::BinaryHeap;
        let n = n as usize;
        let mut g = vec![vec![]; n];
        for e in &edges {
            let (u, v, w) = (e[0] as usize, e[1] as usize, e[2]);
            g[u].push((v, w));
            g[v].push((u, w));
        }
        let dijkstra = |src: usize| -> Vec<i64> {
            let mut d = vec![i64::MAX; n];
            d[src] = 0;
            let mut pq = std::collections::BinaryHeap::new();
            pq.push((0, src));
            while let Some((du, u)) = pq.pop() {
                let du = -du;
                if du > d[u] { continue; }
                for &(v, w) in &g[u] {
                    let v = v as usize;
                    let w = w as i64;
                    if d[v] > d[u] + w {
                        d[v] = d[u] + w;
                        pq.push((-d[v], v));
                    }
                }
            }
            d
        };
        let d1 = dijkstra(0);
        let d2 = dijkstra(n-1);
        let shortest = d1[n-1];
        edges.iter().map(|e| {
            let u = e[0] as usize;
            let v = e[1] as usize;
            let w = e[2] as i64;
            d1[u] + w + d2[v] == shortest || d1[v] + w + d2[u] == shortest
        }).collect()
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32


class Solution {
    findAnswer(n: number, edges: number[][]): boolean[] {
        const g: [number, number][][] = Array.from({length: n}, () => []);
        for (const [u, v, w] of edges) {
            g[u].push([v, w]);
            g[v].push([u, w]);
        }
        function dijkstra(src: number): number[] {
            const d = Array(n).fill(Infinity);
            d[src] = 0;
            const pq: [number, number][] = [[0, src]];
            while (pq.length) {
                pq.sort((a, b) => a[0] - b[0]);
                const [du, u] = pq.shift()!;
                if (du > d[u]) continue;
                for (const [v, w] of g[u]) {
                    if (d[v] > d[u] + w) {
                        d[v] = d[u] + w;
                        pq.push([d[v], v]);
                    }
                }
            }
            return d;
        }
        const d1 = dijkstra(0);
        const d2 = dijkstra(n-1);
        const shortest = d1[n-1];
        return edges.map(([u, v, w]) =>
            d1[u] + w + d2[v] === shortest || d1[v] + w + d2[u] === shortest
        );
    }
}

Complexity

⏰ Time complexity: O((n+m)log n), due to Dijkstra’s algorithm run twice and edge checks.
🧺 Space complexity: O(n+m), for graph and distance arrays.

Problem#

Examples#

Example 1#

Example 2#

Constraints#

Solution#

Method 1 – Dijkstra + Path Backtracking 1#

Intuition#

Approach#

Code#

Complexity#