Understanding Dijkstra’s Algorithm

8 min readJan 17, 2019

In a previous article, I explained the basics of the graph data structure. I mentioned that understanding how to model and traverse a graph is very important because of its many applications throughout the web. In this article, we’ll explore Dijkstra’s Algorithm — which is an algorithm that maps the shortest path between two nodes on a graph.

The Problem

Suppose you have the following graph structure and you want to know the fastest route between nodes A and E. How would you go about determining it?

Because there are only six nodes on this graph it is pretty easy to quickly look at it and determine the fastest route. But, imagine there were a million nodes on this graph. In that case, we would need a step by step process that a computer could follow to determine the shortest path. Enter Dijkstra’s Algorithm.

An Overview

The overall strategy of the algorithm is as follows. Given a starting node, compute the distance of each of its connections (called edges). Whichever connection is the shortest follow it while keeping a running tally of the total distance traveled along that particular path. Repeat until you converge on the final node you’re interested in.

So, if we’re interested in moving from A to E we start with all the connections of A which are B and C. The distance to C is two and the distance to B is four. Two is smaller than four so we move to node C. We now update our path asA -> C and our running total is 2.

We now examine all our possible options. Moving from A to B is still four. Moving from C to D is four and moving from C to F is six (remember, we add the new connection’s distance to our total — which is the distance from A).

Since six is greater than four, we know C to F is out. We now choose randomly between A -> B and C -> D. Suppose we choose C -> D. We update our path and total — path: A -> C -> D total: 4.

We now examine all of our options. A -> B is still four, D -> F is five and D -> E is seven. Four is the lowest so we chose this route. At this point, hopefully the general steps of the algorithm make sense. You might also be asking, how should we keep track of the various routes and distances that we are building. The next section will begin to introduce how we can model this in code.

Modeling in Code

We’ll need three main data structures.

Distance Hash Table: We’ll need a table that maps each nodes total distance from the starting node. The key will be the node and the value will be its running total.
Priority Queue: When we compare all the possible routes we could take, the priority queue will surface the smallest possible route. In this way, we don’t have to scan an array every time asking, which is the smallest.
Routes Hash Table: We need a way to keep track of the current path we’re building. The key will be the current node we are at and its value will be the node it came from.

Visualizing the Algorithm

I’ll show a series of images which highlight the algorithm working and noting the three data structures at play.

This is the current state after analyzing our first options — moving to B or moving to C.

We initialize the starting node (aka vertex) with ZERO and all the other routes with Infinity. This ensures that the first time through, the priority queue starts with our desired node — A.

It’s also important to note that we ONLY update a given node in the distance hash table when we encounter a new route that is smaller than what it currently has set. For example A -> B is four. But, we could also get to B by traveling A -> C -> D -> E -> B which would be 10. Since four is less than 10, we ignore this possible route and would not update B’s total should that appear as an option.

So, we move from A to C.

This is our current state after our second pass through the algorithm. As you can see, we can chose to travel to B or to D as both are four. Let’s chose B so we can see how the distances tables stores each possible route.

This is our state after the third pass through our algorithm. We skipped a step which was when we moved to B. Which is why the current value of B is crossed out and the value of E is seven — A -> B -> E = 7. Sorry!

At this point, we only have two options. Move from D to F which gives us a total of five or move from D to E which gives us a total of seven. Five is less than seven, so we chose this path.

In the final fourth pass through the algorithm, we only have one possible move left — F to E. We now move to E an we’re done!

I know these images are not the clearest as there is a lot going on. But, keep walking through it with pen and paper and it will eventually click.

Code Implementation

Create a function that accepts a start and end point.
Initialize the distance hash table, the priority queue, the routes hash table and a path’s array (we’ll push the name of the nodes in here at the end when building our return value).
Create the starting state for the distance hash table. It should store every node as a key with its initial value set to infinity except for the starting node, which should be 0.
Create the starting state for the priority queue. It should look similar to the hash table — every node should exist with a starting value of infinity except for the start node — it should be 0. This makes sense b/c our priority queue should be a reflection of our distance hash table.
Create the starting state for the routes hash which I’ll call previous. It should have a key for every node and the value should be set to null.
Create a loop which runs as long as there are nodes in the priority queue.
Dequeue a node, it should be the smallest — b/c of the priority queue.
If that node is the same as the ending node, we’re done! Loop through the routes hash table and build the final path.
If not the ending node, find all the connections associated with this node. Add up their totals. If the total is less than what is already stored for it, update it and update the previous hash table.
Create new nodes which pass in the node name and its new total distance to the priority queue (these are a reflection of the distance hash table).
This should run until you hit your conditional from step 8. Now, loop through the previous hash table — starting with the final node name (in our case E) — pushing each key into your path array. Reverse the array and return it.

That’s a ton, I know. Here’s the implementation code so you can walk through it.

class WeightedGraph {
    constructor(){
        this.list = {}
    }    addVertex(v){
        if (!this.list[v]) this.list[v] = []
    }    addEdge(v1, v2, priority){
        let node1 = new Node(v1, priority)
        let node2 = new Node(v2, priority)
        if (this.list[v1]) this.list[v1].push(node2)
        if (this.list[v2]) this.list[v2].push(node1)
    }    shortestPath(start, end){
        //creating the initial data structures
        let distances = {}
        let nodes = new PriorityQueue()
        let previous = {}
        let path = []        //setting the initial state for data structures
        Object.keys(this.list).forEach(nodeName => {
            if (nodeName === start){
                distances[nodeName] = 0
                nodes.enqueue(nodeName, 0)
            } else {
                distances[nodeName] = Infinity
                nodes.enqueue(nodeName, Infinity)
            }
            previous[nodeName] = null
        })        let smallest;
        while (nodes.values.length > 0) {
            //smallest value b/c of priority queue logic
            smallest = nodes.dequeue().value
            //we've reached the end
            if (smallest === end){ 
            //finishing code to determine the path, 
            //traversing the previous hash table
                while (previous[smallest]) {
                    path.push(smallest)
                    smallest = previous[smallest]    
                }
                path.push(smallest)
                break;
            }        if(smallest || distances[smallest] !== Infinity) {
            // finding each of the node's connections
            this.list[smallest].forEach(node => {
                //computing the new distance - current total 
                // + new distance
                let newestDistance = distances[smallest] + node.priority
                let currentDistance = distances[node.value]                    //a new lower distance, update hash 
                    // tables and add to queue
                    if (newestDistance < currentDistance) {
                        distances[node.value] = newestDistance
                        previous[node.value] = smallest;
                        nodes.enqueue(node.value, newestDistance);
                    }
                    
                })
            }
        }
        return path.reverse();
    }
}

Now, in order for this code to work, you’ll also need the setup code for the priority queue and the node class. If you want a walk through of how a binary heap works to create a priority queue, see my article here: https://medium.com/@verdi/binary-heap-basics-40a0f3f41c8f

class Node {
    constructor(value, priority){
        this.value = value;
        this.priority = priority;
    }
}class PriorityQueue{
    constructor(){
        this.values = []
    }    swap(idx1, idx2) {
        let temp = this.values[idx1]
        this.values[idx1] = this.values[idx2]
        this.values[idx2] = temp
    }    enqueue(value, priority) {
        let newNode = new Node(value, priority)
        //How to find parent elements: Math.floor((n-1)/2)
        //smallest priority bubbles up
        this.values.push(newNode)
        if (this.values.length === 1) return this;
        
        let childIdx = this.values.length-1
        let parentIdx = Math.floor((childIdx-1)/2)
        let child = this.values[childIdx].priority
        let parent = this.values[parentIdx].priority        while(child < parent && childIdx > 0){
            this.swap(childIdx, parentIdx)
            childIdx = parentIdx
            parentIdx = Math.floor((childIdx-1)/2)
            parent = this.values[parentIdx]
        }        return this;
    }    dequeue(){
        //How to find child elements: 2n+1, 2n+2
        //biggest priority number (least important) sinks down
        if (this.values.length === 0) return undefined
        if (this.values.length === 1) return this.values.pop();
        if (this.values.length === 2) return this.values.shift();        this.swap(0, this.values.length-1)
        let removedValue = this.values.pop();
        let minChildIdx = null        while (true){
            let parentIdx = minChildIdx || 0
            let parent = this.values[parentIdx].priority
            let child1Idx = Math.floor((2*parentIdx)+1)
            let child2Idx = child1Idx+1            if (child1Idx >= this.values.length) {
                break
            }
            
            let child1 = this.values[child1Idx].priority
            let child2 = child2Idx < this.values.length ? this.values[child2Idx].priority : Infinity    
           
            let minChild = Math.min(child1, child2)
            minChildIdx = this.values[child1Idx].priority === minChild ? child1Idx : child2Idx
            
            if (parent > minChild) {
                this.swap(parentIdx, minChildIdx)
            } else {
                break
            }
        }        return removedValue;
    }
}