Dijkstra Algorithm in JavaScript, heap based fast implementation

Let’s pick up from where we left off and revisit the problem Dijkstra algorithm aims to solve.

Input: directed graph G = (V, E) in adjacency-list representation, a source vertex sV, a length le ≥ 0 for each eE.

Output: the true shortest-path distance to every vertex v from the source vertex s, dist(s, v).

In our slower version of the algorithm, we use a set (with only unique vertices) to keep track of which vertices we’ve already processed. In each iteration, the set gets a new vertex used to calculate the shortest distance to that point. Afterward, we have to look through these processed vertices to find the next best neighbor vertex (out of all the processed ones in the set) and determine the shortest distance value. This process repeats.

When we face a situation where we need to compute the minimum value in every iteration, another tool can step in and significantly speed up these calculations. That tool is the priority queue, particularly in Dijkstra algorithm, where the min heap priority queue proves useful.

The Dijkstra’s specific version of min heap

In this post, we’ll create a specific min priority queue (I’m using JavaScript and there’s no such thing as a priority queue built in JavaScript so we have to create one ourself). This special queue will help us extract the vertex with the current smallest distance, starting from the source vertex.

For a more general understanding of a min heap, you can refer to this post.

In the implementation of a min heap in Dijkstra algorithm, we opt for a key-value pair approach rather than directly storing numeric values. Each object in the heap comprises a pair, where the first key corresponds to the vertex, and the second key represents the calculated distance of that vertex from the source vertex. This adaptation aligns with the intrinsic characteristics of a heap, particularly a min heap, ensuring adherence to priority queue invariants. Consequently, the vertex with the smallest distance value becomes the foremost element in the heap, maintaining the desired order.

class DijkstraMinHeap {
  constructor() {
    this.keys = [];
  }

  insert(key) {
    this.keys.push(key);
    this._heapifyUp(this.keys.length - 1, this.keys);
    return this;
  }

  extractMin() {
    this._swap(this.keys, 0, this.keys.length - 1);
    let temp = this.keys.pop();
    if (this.keys.length) this._heapifyDown(0, this.keys);
    return temp;
  }

  _heapifyUp(index, array) {
    if (index <= 0) return;

    let { distance: currentDistance } = array[index];
    let parentIndex =
      index % 2 === 0 ? (index - 2) / 2 : Math.floor((index - 1) / 2);
    let { distance: parentDistance } = array[parentIndex];
    if (currentDistance < parentDistance) {
      this._swap(array, index, parentIndex);
    }
    this._heapifyUp(parentIndex, array);
  }

  _heapifyDown(index, array) {
    let { distance: parentDistance } = array[index];
    let leftIndex = 2 * index + 1;
    if (leftIndex >= array.length) return; // Check if left child index is out of bounds
    let { distance: leftDistance } = array[leftIndex];
    let rightIndex = 2 * index + 2;
    let rightDistance;
    if (rightIndex < array.length) {
      rightDistance = array[rightIndex].distance;
    }

    if (parentDistance > leftDistance || parentDistance > rightDistance) {
      if (!rightDistance || leftDistance <= rightDistance) {
        this._swap(array, leftIndex, index);
        this._heapifyDown(leftIndex, array);
      } else {
        this._swap(array, rightIndex, index);
        this._heapifyDown(rightIndex, array);
      }
    }
  }

  _swap(array, index1, index2) {
    let temp = array[index1];
    array[index1] = array[index2];
    array[index2] = temp;
  }
}

export default DijkstraMinheap;

Heap based Dijkstra algorithm

import DijkstraMinHeap from "./DijkStraMinHeap";

class HeapBasedDijkstra extends WeightedGraph {
  heapBasedDijkstra(start, end) {
    let known = new Set();
    let dist = {};
    let prev = {};
    let heap = new DijkstraMinHeap();
    dist[start] = 0;
    const vertices = Object.keys(this.adjacencyList);
    vertices.forEach((v) => {
      if (v !== start) dist[v] = Infinity;
    });
    heap.insert({ vertex: start, distance: dist[start] });

    while (heap.keys.length) {
      let current = heap.extractMin();
      let { vertex, distance: prevShortestDistance } = current;

      if (!known.has(vertex)) {
        known.add(vertex);

        this.adjacencyList[vertex].forEach((neighbor) => {
          let { vertex: neighborVertex, length } = neighbor;
          let newDistance = prevShortestDistance + length;
          dist[neighborVertex] = Math.min(dist[neighborVertex], newDistance);
          prev[neighborVertex] =
            dist[neighborVertex] === newDistance
              ? vertex
              : prev[neighborVertex];
          heap.insert({
            vertex: neighborVertex,
            distance: dist[neighborVertex],
          });
        });
      }
    }

    let path = [];
    for (let at = end; at !== undefined; at = prev[at]) {
      path.push(at);
    }
    path = path.reverse();

    return {
      path,
      length: dist[end],
    };
  }
}

export default HeapBasedDijkstra;

Notice how the slow and fast versions are quite similar. The big change is that now we’re using the handy min heap we built earlier. Instead of going through the trouble of comparing and calculating to find the smallest distance among the neighboring vertices each time, in the fast version, we get the vertex with the smallest distance effortlessly. This happens quickly, in O(logn) time, which is way better than the O(m) time it took in the slower version.

One additional subtle adjustment to note: instead of precluding the source vertex from the “known” set prior to entering the primary while loop, as was the case in the slower version, the set is now initialized as empty before the main loop. If the source vertex were added to the known set before the primary loop, the remaining vertices in the graph would remain unexplored. In this scenario, all distances from the source vertex to other vertices would persist as +∞ (as you should verify).

Here’s an example graph for our Dijkstra implementation (I drew it 😃 ):

import HeapBasedDijkstra from "./HeapBasedDijkstra";

const graph = new HeapBasedDijkstra();

// Add vertices
graph.addVertex("A");
graph.addVertex("B");
graph.addVertex("C");
graph.addVertex("D");
graph.addVertex("E");

// Add directed edges with weights
graph.addEdge("A", "B", 4);
graph.addEdge("A", "C", 2);
graph.addEdge("B", "E", 3);
graph.addEdge("C", "D", 2);
graph.addEdge("D", "E", 2);

// Find the shortest path from vertex "A" to "E"
const result = dijkstra.heapBasedDijkstra("A", "E");

// Print the result
console.log("Shortest Path:", result.path); // ["A","C","D","E"]
console.log("Shortest Length:", result.length); // 6

To wrap up our talk about the heap-based Dijkstra algorithm, the total time it takes at its slowest is roughly O(mlogn).


Posted

in

by