Find edges in shortest paths

Depth-First Search Breadth-First Search Graph Theory Heap (Priority Queue) Shortest Path

46.4% acceptance

Feb 23, 2026

309

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.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

use std::collections::BinaryHeap;
use std::cmp::Reverse;

impl Solution {
  fn dijkstra(adj: &Vec<Vec<(usize, i64)>>, start: usize) -> Vec<i64> {
    let n = adj.len();
    let mut dist = vec![i64::MAX; n];
    dist[start] = 0;
    let mut heap = BinaryHeap::new();
    heap.push(Reverse((0i64, start)));
    while let Some(Reverse((d, u))) = heap.pop() {
      if d > dist[u] { continue; }
      for &(v, w) in &adj[u] {
        let nd = d + w;
        if nd < dist[v] {
          dist[v] = nd;
          heap.push(Reverse((nd, v)));
        }
      }
    }
    dist
  }

  pub fn find_answer(n: i32, edges: Vec<Vec<i32>>) -> Vec<bool> {
    let n = n as usize;
    let mut adj = vec![vec![]; n];
    for e in &edges {
      let (a, b, w) = (e[0] as usize, e[1] as usize, e[2] as i64);
      adj[a].push((b, w));
      adj[b].push((a, w));
    }

    let dist_from = Self::dijkstra(&adj, 0);
    let dist_to = Self::dijkstra(&adj, n - 1);
    let total = dist_from[n - 1];

    edges
      .iter()
      .map(|e| {
        let (a, b, w) = (e[0] as usize, e[1] as usize, e[2] as i64);
        if total == i64::MAX { return false; }
        (dist_from[a] != i64::MAX && dist_to[b] != i64::MAX && dist_from[a] + w + dist_to[b] == total)
        || (dist_from[b] != i64::MAX && dist_to[a] != i64::MAX && dist_from[b] + w + dist_to[a] == total)
      })
      .collect()
  }
}