Data Structures and Algorithms: Dijkstra's Algorithm

Introduction

Dijkstra's Algorithm is a greedy algorithm that is used to find the shortest path from a source vertex to all of the other vertices on a weighted directed graph. Being a greedy algorithm, an attempt is made to find the optimal solution by breaking the problem up into steps and solving these steps one at a time. The optimal solution in this case is the next vertex with shortest path. It is important to note that this algorithm cannot be used in a graph with negative weights.

Dijkstra's Algorithm Walkthrough

The algorithm starts by initialising the starting vertex of the graph with a distance of zero and all other vertices with distances of infinity. At this point all of the vertices are marked as unvisited. The algorithm will also initialise a priority queue to keep track of the vertices with the shortest known distances. The starting vertex is then dequeued(as it has a distance of zero) and is marked as visited. The algorithm will now check the edges of the adjacent vertices, calculating a new potential distance to each vertex by adding the weight to the distance from the current vertex. If the new distance is smaller than the currently known distance to the vertex, this distance is updated and the vertex is enqueued. The algorithm will then go on to select the next vertex from the priority queue(i.e. the vertex with the smallest distance), mark it as visited and will repeat the process until all of the vertices in the graph have been visited. We can illustrate this using the following graph:

Starting at vertex A with a distance of zero, the distances from A to all of the remaining vertices will be set as infinity. A is then added to a priority queue, before being dequeued, marked as visited and checking the distances to vertices B and D. As these distances are less than infinity, their calculated distances are updated as 2 and 6 respectively. Both vertices are then added to the priority queue.

As B has the shortest distance, it will be the next vertex to be dequeued, marked as visited and processed by the algorithm. The algorithm now checks B's adjacent vertices(D and C) and checks their distances from the starting node, A -> B -> C(2 + 3 = 5) and A -> B -> D(2 + 7 = 9). The algorithm then compares these newly calculated distances to the previously stored distances. The distance to C is updated to 5 and the distance to D remains unchanged at 6. C is now also added to the priority queue.

The shortest distance is now 5 so the vertex C is dequeued and marked as visited. It only has E as an adjacent vertex, with a distance of 2 + 3 + 5 = 10(A -> B -> C -> E). The vertex E is also added to the priority queue.

D is the next vertex to be dequeued and marked as visited since it has a distance of 6(A -> D). The algorithm will now check D's adjacent vertices. Vertex C has already been visited so no further action will be taken. Finally the algorithm will finish by dequeuing E and processing it.

Implementing Dijkstra's Algorithm in JavaScript

To implement Dijkstra's Algorithm in JavaScript, we can start off by creating a PriorityQueue class.

class PriorityQueue {
  constructor() {
    this.elements = [];
  }

  enqueue(node, weight) {
    this.elements.push({ node, weight });
    this.elements.sort((a, b) => a.weight - b.weight);
  }

  dequeue() {
    return this.elements.shift(); 
  }

  isEmpty() {
    return this.elements.length === 0;
  }
}

Along with the constructor, we will create an enqueue() method to add a vertex and its weight to the priority queue. These vertices are then sorted according to their weights, that is to say, the vertex with the smallest weight(or distance) will come first. The dequeue() method is used to return the vertex with the smallest weight from the priority queue and the isEmpty() method is used to check if the priority queue has any vertices.

Next we will create a Graph class which will have a constructor. This constructor will use an object to store an adjacency list.

  constructor() {
    this.adjacencyList = {}; 
  }

The Graph class will also have the addNode() method which will be used to add a vertex and the addEdge() method which will be used to add edges to a vertex.

  addNode(node) {
    this.adjacencyList[node] = [];
  }

  addEdge(node1, node2, weight) {
    this.adjacencyList[node1].push({ node: node2, weight });
  }

The addNode() method will initialize an empty array for the adjacency list for a given vertex. This array will then go on to store all of the edges for the node provided in the addEdge() method. For example, to add nodes A and B from our graph, we will use:

graph.addNode('A');
graph.addNode('B');

The adjacency lists for the two nodes will look like this:

{
  A: [],
  B: []
}

And then the edge can be added as follows

graph.addEdge('A', 'B', 2);

This results in the adjacency list looking like this:

{
  A: [{ node: 'B', weight: 2 }],
}

We will also need to create the dijkstra() method to run the algorithm:

dijkstra(start) {
    const distances = {};
    const previous = {};
    const pQueue = new PriorityQueue();

    for (const node in this.adjacencyList) {
      distances[node] = Infinity;
      previous[node] = null;
    }

    distances[start] = 0;
    pQueue.enqueue(start, 0);

    while (!pQueue.isEmpty()) {
      const { node: currentNode } = pQueue.dequeue();

      for (const neighbor of this.adjacencyList[currentNode]) {
        const { node: adjacent, weight } = neighbor;
        const newDist = distances[currentNode] + weight;

        if (newDist < distances[adjacent]) {
          distances[adjacent] = newDist;
          previous[adjacent] = currentNode;
          pQueue.enqueue(adjacent, newDist); 
        }
      }
    }

   return { distances, previous };
  }

This method will have a distances object to map the calculated distances from the starting vertex to all of the remaining vertices in the graph, a previous object to keep track of each vertex's previous vertex and a priority queue which will be used to keep track of the vertices with the shortest distances. These will be initialised and the distances from the starting vertex will be calculated, before returning the distances and previous objects.

Lastly we will create the getShortestPath() method, which will be used to return the shortest path between two vertices.

 getShortestPath(start, end) {
    const { distances, previous } = this.dijkstra(start);
    const path = [];
    let currentNode = end;

    while (currentNode !== null) {
      path.push(currentNode);
      currentNode = previous[currentNode];
    }

    return {
      distance: distances[end],
      path: path.reverse(),
    };
  }

Conclusion

This article explains the logic behind Dijkstra's Algorithm to find the shortest path in a graph. This article also shows how the algorithm can be implemented in JavaScript using a priority queue, although this could be done more efficiently using a min-heap. Some real world applications of Dijkstra's Algorithm include GPS and mapping software(Google Maps), route optimization in public transport systems, finding the most efficient route for sending data packets in internet routing protocols and AI pathfinding in video games.