Design graph with shortest path calculator

Graph Theory Design Heap (Priority Queue) Shortest Path

64.9% acceptance

Feb 23, 2026

875

There is a directed weighted graph that consists of n nodes numbered from 0 to n - 1. The edges of the graph are initially represented by the given array edges where edges[i] = [fromi, toi, edgeCosti] meaning that there is an edge from fromi to toi with the cost edgeCosti. Implement the Graph class: Graph(int n, int[][] edges) initializes the object with n nodes and the given edges. addEdge(int[] edge) adds an edge to the list of edges where edge = [from, to, edgeCost]. int shortestPath(int node1, int node2) returns the minimum cost of a path from node1 to node2. If no path exists, return -1. The cost of a path is the sum of the costs of the edges in the path.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

pub struct Graph {
  n: usize,
  adj: Vec<Vec<(usize, i64)>>,
}

impl Graph {
  pub fn new(n: i32, edges: Vec<Vec<i32>>) -> Self {
    let n = n as usize;
    let mut adj = vec![vec![]; n];
    for e in edges {
      adj[e[0] as usize].push((e[1] as usize, e[2] as i64));
    }
    Graph { n, adj }
  }

  pub fn add_edge(&mut self, edge: Vec<i32>) {
    self.adj[edge[0] as usize].push((edge[1] as usize, edge[2] as i64));
  }

  pub fn shortest_path(&self, node1: i32, node2: i32) -> i32 {
    // Dijkstra
    use std::collections::BinaryHeap;
    use std::cmp::Reverse;

    let src = node1 as usize;
    let dst = node2 as usize;
    let mut dist = vec![i64::MAX; self.n];
    dist[src] = 0;
    let mut heap = BinaryHeap::new();
    heap.push(Reverse((0i64, src)));

    while let Some(Reverse((d, u))) = heap.pop() {
      if d > dist[u] { continue; }
      if u == dst { return d as i32; }
      for &(v, w) in &self.adj[u] {
        let nd = d + w;
        if nd < dist[v] {
          dist[v] = nd;
          heap.push(Reverse((nd, v)));
        }
      }
    }
    if dist[dst] == i64::MAX { -1 } else { dist[dst] as i32 }
  }
}