Dijkstra’s Algorithm in JavaScript, slow implementation

Dijkstra’s Algorithm is a handy tool for figuring out the shortest path in a connected directed graph where each connection has a non-negative weight. If you’re familiar with Prim’s Minimum Spanning Tree, despite having different goals, you’ll observe that both employ a greedy strategy to carefully select the optimal/smallest distance path step by step.

Note: Before we dive in, make sure you’re comfortable with the Graph data structure, especially the adjacency list. If you’re not, check out this post before continuing.

Making our graph weighted

To prepare for Dijkstra’s Algorithm, we need to tweak our Graph implementation to handle directed weighted edges. The new WeightedGraph class does just that:

import WeightedGraph from "./Graph";

class WeightedGraph extends Graph {
  addEdge(v1, v2, length) {
    if (this.adjacencyList[v1] && this.adjacencyList[v2]) {
      this.adjacencyList[v1].push({
        vertex: v2,
        length,
      });
      this.adjacencyList[v2].push({
        vertex: v1,
        length,
      });
      return true;
    }
    return false;
  }

  addDirectedEdge(v1, v2, length) {
    if (this.adjacencyList[v1] && this.adjacencyList[v2]) {
      this.adjacencyList[v1].push({
        vertex: v2,
        length,
      });
      return true;
    }

    return false;
  }
  
  removeEdge(v1, v2) {
    if (this.adjacencyList[v1] && this.adjacencyList[v2]) {
      this.adjacencyList[v1] = this.adjacencyList[v1].filter(
        (v) => v.vertex !== v2
      );
      this.adjacencyList[v2] = this.adjacencyList[v2].filter(
        (v) => v.vertex !== v1
      );
      return true;
    }
    return false;
  }

  removeDirectedEdge(v1, v2) {
    if (this.adjacencyList[v1] && this.adjacencyList[v2]) {
      this.adjacencyList[v1] = this.adjacencyList[v1].filter(
        (v) => v.vertex !== v2
      );
      return true;
    }
    return false;
  }
}

module.exports = WeightedGraph;

Naive Slow Dijkstra implementation

For smaller graphs (we’re talking about thousands of vertices, not millions), a straightforward version of Dijkstra’s Algorithm works just fine. Even when dealing with bigger graphs, this straightforward approach still gets the job done, although not so efficient.

Before we look at the code, let’s understand the problem:

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).

Here’s the straightforward/slow Dijkstra’s Algorithm implemented in JavaScript:

import WeightedGraph from "./WeightedGraph";

class SlowDijkstra extends WeightedGraph {
  computeShortestPath(start, end) {
    let known = new Set(); // a new Set contains distinct vertices
    known.add(start);
    let dist = {}; // true shortest path distances
    let prev = {}; // for backtracking to construct a path
    dist[start] = 0;
    for (let v in this.adjacencyList) {
      if (v != start) {
        dist[v] = Infinity;
      }
    }
    
    // consider a *connected* directed weighted graph
    while (known.size < Object.keys(this.adjacencyList).length) {
      let min = Infinity;
      let nextVertex = null;
      let prevVertex = null;
      known.forEach((vertex) => {
        this.adjacencyList[vertex].forEach((neighbor) => {
          const { vertex: neighborVertex, length } = neighbor;
          if (!known.has(neighborVertex)) {
            let len = dist[vertex] + length;
            if (len < min) {
              min = len;
              nextVertex = neighborVertex;
              prevVertex = vertex;
            }
          }
        });
      });

      dist[nextVertex] = min;
      known.add(nextVertex);
      prev[nextVertex] = prevVertex;
    }
    
    let path = [];

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

export default SlowDijkstra;

This implementation initially establishes a set named known to track explored vertices. We initiate our exploration of the graph from the starting vertex, hence adding the start vertex to the known set is logical.

The algorithm then initializes distance dist and predecessor prev key-value pairs objects.

The variable dist is responsible for assigning the distance from the starting vertex to itself as 0, with all other distances set to infinity.

Meanwhile, prev is reserved for a specific purpose – it will be used in constructing a path from the start vertex to the end vertex. This comes into play after completing the computation of the shortest path distances from the start vertex to all reachable vertices in the connected graph, as assumed in our approach.

Dijkstra’s Algorithm’s core lies in the iteration process, where the next vertex to explore is pinpointed by examining neighbors of vertices in the known set. The algorithm selects the neighbor vertex with the minimum distance, calculates and stores its true shortest distance to the dist, and adds the vertex to the known set.

Upon completing iterations, the algorithm constructs the shortest path from the end vertex to the start vertex by backtracking through the predecessor prev information. The resulting path is reversed to maintain the correct order, and the distance of the shortest path is calculated.

The time complexity for the algorithm is O(mn), with m denoting the number of edges and n representing the number of vertices.

While this implementation correctly executes Dijkstra’s algorithm, its efficiency could be enhanced for larger graphs by incorporating a priority queue/heap data structure for a more streamlined selection of the next vertex.

And that’s what we discuss here.


Posted

in

by