Dijkstra’s Shortest Path Algorithm

Complexity: O(V) — create arrays, O(log V) — hasUnvisited and getLowestUnvisited using an ‘unseen’ condition (O(V²) without it), while-edge loop is O(E). The composite optimized complexity is O(log V (V + E))

type GraphEdge = {to: number, weight: number}
type WeightedAdjacencyList = GraphEdge[][]

function hasUnvisited(seen: boolean[], dists: number[]): boolean {
  return seen.some((s, i) => !s && dists[i] < Infinity) // Infinity < Infinity >>> false
}

function getLowestUnvisited(seen: boolean[], dists: number[]): number {
  let ind = -1
  let lowestDistance = Infinity
  
  for (let i = 0; i < seen.length; ++i) {
    if (seen[i]) {
      continue
    }

    if (lowestDistance > dists[i]) {
      lowestDistance = dists[i]
      ind = i
    }
  }

  return ind
}

// works only with non-negative digits
function dijkstraList(
  source: number, // first element
  pointer: number, // final element
  graph: WeightedAdjacencyList
): number[] {
  
  const seen = new Array(arr.length).fill(false)
  const prev = new Array(arr.length).fill(-1)
  const dists = new Array(arr.length).fill(Infinity)

  dists[source] = 0

  while (hasUnvisited(seen, dists)) {
    const cur = getLowestUnvisited(seen, dists)

    seen[cur] = true
  
    const adjs = graph[cur]
    for (let i = 0; i < adjs.length; ++i) {

      const edge = adjs[i]
      if (seen[edge.to]) {
        continue
      }
      
      const dist = dists[cur] + edge.weight
      if (dist < dists[edge.to]) {
        dists[edge.to] = dist
        prev[edge.to] = cur
      }
    }
  }

  const out: number[] = []
  let cur = pointer

  while (prev[cur] !== -1) {
    out.push(cur)
    cur = prev[cur]
  }

  out.push(source)
  return out.reverse()
}