LeetCode Entry

2642. Design Graph With Shortest Path Calculator

11.11.2023 hard 2023 kotlin

Implement graph with shortest path searching

2642. Design Graph With Shortest Path Calculator hard blog post substack image.png

Problem TLDR

Implement graph with shortest path searching

Intuition

There is no special knowledge here, just a simple Dijkstra, that is BFS in a space of the shortest-so-far paths

Approach

  • the visited set will improve the speed

Complexity

  • Time complexity: \(O(Vlog(E))\)

  • Space complexity: \(O(E)\)

Code


class Graph(n: Int, edges: Array<IntArray>) :
  HashMap<Int, MutableList<IntArray>>() {
  init { for (e in edges) addEdge(e) }

  fun addEdge(edge: IntArray) {
    getOrPut(edge[0]) { mutableListOf() } += edge
  }

  fun shortestPath(node1: Int, node2: Int): Int =
    with(PriorityQueue<Pair<Int, Int>>(compareBy({ it.second }))) {
      add(node1 to 0)
      val visited = HashSet<Int>()
      while (isNotEmpty()) {
        val (n, wp) = poll()
        if (n == node2) return@with wp
        if (visited.add(n))
          get(n)?.onEach { (_, s, w) -> add(s to (w + wp))}
      }
      -1
    }
}