Skip to content
he110
Back to blog

Algorithm Notes

Study notes on graph traversal, shortest-path solving, and hash collision handling, with code examples and implementation ideas.

Updated

Dijkstra's Shortest Path Algorithm

Dijkstra is essentially a breadth-first search algorithm.

Starting from the most basic breadth-first search on a binary tree, the basic structure looks like:

function bfs(root: TreeNode | null) {
  const queue: TreeNode[] = root ? [root] : []

  while (queue.length) {
    const len = queue.length
    for (let i = 0; i < len; ++i) {
      // This is where each node gets visited
      const node = queue.shift()

      // Enqueue the next level of nodes
      if (node.left) {
        queue.push(node.left)
      }
      if (node.right) {
        queue.push(node.right)
      }
    }
  }
}

When we extend the binary-tree breadth-first search to a graph structure, compare the differences between a graph and a binary tree:

  • A binary tree node has at most 2 children; a graph node may have infinitely many.
  • A binary tree's children cannot be visited repeatedly; a graph's nodes may be visited more than once.
  • When a binary tree traversal reaches a given node, the state to compute is fixed and unique; in a graph, because nodes are reached via different paths, the values to compute may be inconsistent.

Generally speaking, as long as the second difference is solved—never visiting the same node twice—the third difference disappears.

So in general, the breadth-first search for a graph looks like this:

/**
 * @param graph Declares, for elements with IDs 0 - n, which nodes are adjacent to each, i.e. the adjacency list
 */
function bfs(graph: number[][], startNodeID: number) {
  const n = graph.length
  const visited = new Array(n).fill(false)
  const queue: number[] = [startNodeID]

  while (queue.length) {
    const len = queue.length

    // A for loop is still used here
    // The purpose is to constrain each outward expansion so that the distance from startNode is the same number of levels
    // That is, assuming the distance between any two points is equal, e.g. always 1
    for (let i = 0; i < len; ++i) {
      // This is where each node gets visited
      const node = queue.shift()
      // Record that this node has been visited; no need to visit it again
      visited[i] = true

      // Enqueue the next level of nodes
      const children = graph[i]
      for (const nextNodeID of children) {
        // Only unvisited nodes are enqueued; this restricts each node to a single visit
        if (!visited[nextNodeID]) {
          queue.push(nextNodeID)
        }
      }
    }
  }
}

This breadth-first search smooths out the structural differences between a binary tree and a graph, but the algorithm has its limits.

Because of the third difference, when the distances between nodes in the graph are unequal, revisiting the same node becomes necessary.

It's like taking the bus: there are usually many routes, direct or with transfers, and all of them reach the destination, but the time it takes differs.

Some are direct but take 1 hour; others require 3–4 transfers but might get there in half an hour.

Choosing a route by one-size-fits-all order of visitation is not acceptable.

So the Dijkstra algorithm was born.

The basic logic of Dijkstra is: breadth-first search + pruning.

interface State {
  /** The ID of the node to visit */
  id: number
  /** Records the state value to aggregate when visiting the current node; in this example, the distance from startNode */
  val: number
}

/**
 * Dijkstra generally solves cases where the distance/cost between nodes differs
 * So besides recording which nodes are adjacent, you also need to record the distance/cost of reaching each node
 * Distance is used as the example here
 * endNodeID is also optional; shortest path can find the shortest path to any node, i.e. the lengths array
 */
function dijkstra(graph: [number, number][][], startNodeID: number, endNodeID: number) {
  const n = graph.length
  const max = Number.MAX_SAFE_INTEGER

  /** Initialize the shortest distance from each node to startNode */
  const lengths = new Array(n).fill(max)
  lengths[startNodeID] = 0

  /**
   * The queue from a plain breadth-first search
   * If a priority queue is available, it can replace the queue here
   * Then the algorithm can end directly upon first reaching the destination
   * Because a priority queue picks the shortest current path among all children to traverse first
   * Since JS has no built-in heap structure, implementing a priority queue yourself is too tedious and is generally not used in algorithm problems
   * Using a plain queue here is also OK; it just adds some traversal rounds. Since the algorithm is Edge * log(Node) level,
   * without a priority queue it falls back to Edge * log(Edge) level; since both are log level, the actual overhead does not increase much
   */
  const states: State[] = []
  states.push({
    id: startNodeID,
    val: lengths[startNodeID],
  })

  while (states.length) {
    const { id, val } = states.shift()

    // If there is a destination, it can be pruned right here; no need to keep traversing
    // This is still a plain queue, so update the shortest path and prune
    if (id === endNodeID) {
      lengths[id] = Math.min(lengths[id], val)
      continue
    }

    // If the distance needed to reach this node is already longer than the minimum recorded before, discard this branch—i.e. prune
    // Pruning already happened inside the for loop, but pruning is still needed here
    // Because a node may be traversed repeatedly: after the for-loop pruning, a smaller length may be updated at the current node
    // So pruning is still needed here
    if (val > lengths[id]) {
      continue
    }

    // Traverse the children
    for (const [nextNodeID, nextNodeStep] of graph[id]) {
      // Compute the distance to the next node
      const length = val + nextNodeStep
      // If the distance to the next node is longer than what is already recorded, there is no need to traverse; prune directly
      // Only traverse when it is smaller than the recorded value
      if (length < lengths[nextNodeID]) {
        // Update the lengths array
        lengths[nextNodeID] = length
        // Add to the pending queue
        states.push({
          id: nextNodeID,
          val: length,
        })
      }
    }
  }

  // If a node's minimum length is still the initial value, it is unreachable; return -1
  return lengths[endNodeID] === max ? -1 : lengths[endNodeID]
}

Hash Collisions

When a Hash function maps values, it cannot fully guarantee that A !== B implies hash(A) !== hash(B). The reason is that the capacity produced by the hash mapping is limited—take hash(x) = x % 10, whose capacity is 10.

When a hash collision occurs, there are two common ways to resolve it:

  • Open addressing: when a slot is occupied, keep probing downward until an empty slot is found. It's like a parking space being taken—you keep driving further in to see whether another space is free. In other words, we avoid existing collisions by introducing new ones.
    • Lookup: find the address from hash, check whether the stored value matches the lookup value, and keep probing if not.
    • Deletion: an element cannot be deleted directly, because the node originally at that slot may have been moved away due to occupation; it can only be marked as deleted, and lookups continue past a deleted mark.
  • Chaining: build a multi-dimensional structure, mapping hash(x) to the head node of a linked list, and chain all values with the same hash together.