Dijkstra's Algorithm on JavaScript

Koowoy

Definition of Dijkstra’s Algorithm

Algorithm to calculate the shortest path from one vertex of a graph to another vertex, using a priority array

Input and Output

  1. Input: starting vertex, ending vertex
  2. Output: an array of vertices consisting of the shortest path from start to end in order

Logic

1. To begin with, 4 variables need to be initialized.

  • distances object: used to store the shortest distance from start to each vertex
  • previous object: used to store the previous vertex of the path shortest to the current vertex
  • priority queue: used to store vertices to pay visits to, in ascending order of distances from the starting vertex to the current vertex, this will be used for looping through the graph
  • path: an array for storing path info at the end for returning the path

2. Initial information for distance object, previous object, and priority queue must be assigned

  • In the beginning the distance for each vertex should be set to Infinity (which will mean the same as nothing in the context)
  • In the beginning the priority queue should consist of all vertices with the priority of Infinity (which will mean the same as nothing in the context)
  • In the beginning the previous for each vertex should be set to null
  • The distance and priority in the priority queue for the starting vertex should be set to 0 (since the loop for finding the path should begin here)

3. Traverse the graph in order of the priority queue

  • while the priority queue is not empty, keep looping
  • dequeue from the priority queue (which will return the first element of the queue, so in this cases the one with the smallest priority = distance) and save it to a current variable
  • if the current variable is valid (if it contains a value and is connected with an edge), loop through all the neighboring vertices
  • the distance to a certain neighboring vertex is the sum of shortest path to current vertex and the distance between the current and the neighbor
  • if this distance is smaller than what is set as the distance until now, replace it in the distance object, update the previous of the neighboring vertex to be current vertex, and enqueue this neighboring vertex with the priority value of the newly updated distance.
  • if the current vertex equals the ending vertex, start from the current vertex, and while tracing back through the previous vertices using the previous object, push each vertex to the path

Steps

1. Define Base Classes: Graph Class, Priority Queue Class

Graph Class

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

    addVertex(vertex) {
        if(!this.adjacencyList[vertex]) this.adjacencyList[vertex] = [];
    }

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

The Graph Class is consisted of an adjacency list, which stores the information of vertices of a graph together with the information of the neighboring vertices. Therefore, when an edge, which is the connection between two vertices, is added, this information is added to each of the vertices.

Priority Queue Class

class Node {
    constructor(val, priority) {
        this.val = val;
        this.priority = priority;
    }
}

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

    enqueue(v, p) {
        let newNode = new Node(v, p);
        this.heap.push(newNode);
        let child = this.heap.length - 1;
        let parent = Math.floor((child - 1) / 2);

        if(this.heap.length > 1) {
            while(child && this.heap[child].priority < this.heap[parent].priority) {
                let temp = this.heap[child];
                this.heap[child] = this.heap[parent];
                this.heap[parent] = temp;
                child = parent;
                parent = Math.floor((child - 1) / 2);
            }
        }

        return this.heap;
    }

    dequeue() {
        let toExtract = this.heap[0];
        (this.heap.length > 1) ? this.heap[0] = this.heap.pop() : this.heap.pop();

        let parentIdx = 0;

        while(true) {
            let childIdxL = 2 * parentIdx + 1;
            let childIdxR = 2 * parentIdx + 2;
            let left, right;
            let swap = null;

            if(childIdxL < this.heap.length) {
                left = this.heap[childIdxL];
                if(left.priority < this.heap[parentIdx].priority) {
                    swap = childIdxL;
                }
            }

            if(childIdxR < this.heap.length) {
                right = this.heap[childIdxR];
                if(right.priority < this.heap[parentIdx].priority) {
                    swap = (swap && this.heap[swap].priority < right.priority) ? swap : childIdxR;
                }
            }

            if(swap === null) break;
            let current = this.heap[parentIdx]
            this.heap[parentIdx] = this.heap[swap];
            this.heap[swap] = current;

            parentIdx = swap;
        }

        return toExtract;
    }
}

Priority queue is a queue that stores data as a tree that sorts the queue in the order of the priority value, each time a node is added or removed.

2. Set up variables in Dijkstra Method

Dijkstras(start, end) {
        const distances = {};
        const pQueue = new PriorityQueue();
        const previous = {};
        let path = [];
        for (let v in this.adjacencyList) {
            if(v === start) {
                distances[v] = 0;
                pQueue.enqueue(v, 0);

            } else {
                distances[v] = Infinity;
                pQueue.enqueue(v, Infinity);
            }
            previous[v] = null;

        }
// ...
}

The above is the basic settings of variables used for traversing the graph.

The distances object store the shortest distances from the starting vertex to each vertex at each stage of the traversal, and is used as the priority value when enqueueing vertices to the priority queue.

The previous object store information of where the shortest path to each vertex comes from. This is used to calculate distances new vertices found in the traversal and for tracing back the path at the end for returning .

The priority queue is where we loop from. every time a vertex is found, and the path we are on now is shorter than what was assigned in the distance object, we enqueue this instance to the priority queue. Because of the characteristics of the priority queue, we will traverse to the vertex with the shortest distance each time in the loop.

3. Loop until the end vertex is met.

//...
        while(pQueue.heap.length){
            let currentV = pQueue.dequeue().val;
            // when the end vertex is reached, break loop
            if (currentV === end){
                while(previous[currentV]) {
                    path.push(currentV);
                    currentV = previous[currentV];
                }
                break;
            }

            // if current vertex is valid, loop each neighboring vertex
            if(currentV || distances[currentV] !== Infinity){
                for (let v of this.adjacencyList[currentV]) {

                    let neighbor = v.node;
                    let weight = v.weight;

                    let d = distances[currentV] + weight;

                    // if the newly found path is shorter in distance than what we currently know, replace
                    if(d < distances[neighbor]) {
                        distances[neighbor] = d;
                        previous[neighbor] = currentV;
                        pQueue.enqueue(neighbor, d)
                    }
                }
            }
        }
// ...
}