Dijkstra Shortest Path Complete Guide

type WeightedEdge = { edgeWeight: number; neighborNode: number }

type HeapNode = { distance: number; node: number }

class MinDistanceHeap {
  private readonly values: HeapNode[] = []

  push(params: HeapNode): void {
    this.values.push(params)
    this.bubbleUp(this.values.length - 1)
  }

  pop(): HeapNode | null {
    if (this.values.length === 0) return null
    const rootValue = this.values[0]
    const lastValue = this.values.pop()
    if (this.values.length > 0 && lastValue) {
      this.values[0] = lastValue
      this.bubbleDown(0)
    }
    return rootValue
  }

  private bubbleUp(startIndex: number): void {
    let currentIndex = startIndex
    while (currentIndex > 0) {
      const parentIndex = Math.floor((currentIndex - 1) / 2)
      if (this.values[parentIndex].distance <= this.values[currentIndex].distance) break
      ;[this.values[parentIndex], this.values[currentIndex]] = [this.values[currentIndex], this.values[parentIndex]]
      currentIndex = parentIndex
    }
  }

  private bubbleDown(startIndex: number): void {
    let currentIndex = startIndex
    while (true) {
      const leftChildIndex = currentIndex * 2 + 1
      const rightChildIndex = currentIndex * 2 + 2
      let smallestIndex = currentIndex

      if (leftChildIndex < this.values.length && this.values[leftChildIndex].distance < this.values[smallestIndex].distance) {
        smallestIndex = leftChildIndex
      }
      if (rightChildIndex < this.values.length && this.values[rightChildIndex].distance < this.values[smallestIndex].distance) {
        smallestIndex = rightChildIndex
      }
      if (smallestIndex === currentIndex) break

      ;[this.values[currentIndex], this.values[smallestIndex]] = [this.values[smallestIndex], this.values[currentIndex]]
      currentIndex = smallestIndex
    }
  }
}

function dijkstraShortestDistances(params: { adjacencyByNode: WeightedEdge[][]; sourceNode: number }): number[] {
  const distanceByNode = new Array<number>(params.adjacencyByNode.length).fill(Number.POSITIVE_INFINITY)
  distanceByNode[params.sourceNode] = 0

  const frontierHeap = new MinDistanceHeap()
  frontierHeap.push({ distance: 0, node: params.sourceNode })

  while (true) {
    const nextEntry = frontierHeap.pop()
    if (!nextEntry) break

    if (nextEntry.distance !== distanceByNode[nextEntry.node]) {
      continue
    }

    for (const edge of params.adjacencyByNode[nextEntry.node]) {
      const candidateDistance = nextEntry.distance + edge.edgeWeight
      if (candidateDistance < distanceByNode[edge.neighborNode]) {
        distanceByNode[edge.neighborNode] = candidateDistance
        frontierHeap.push({ distance: candidateDistance, node: edge.neighborNode })
      }
    }
  }

  return distanceByNode
}