Dijkstra's algorithm is an algorithm for finding the shortest path between nodes in a graph, such as road networks. It was conceived by computer scientist Edsger W. Dijkstra in 1956.

This post does not go into great detail about the algorithm, but what it does do is provide an interactive application (found at the bottom of the post) that offers insight into how the usual visualisation of nodes and edges (found in most explanations) are translated into a coded data structure.

The application also shows how the data structure is updated, whilst the algorithm iterates through to completion until the result is returned.

For a more in depth breakdown of the algorithm, if you have not been studying it you can read this post

My example and data structure for the graph was taken from the book, grokking algorithms The book's implementation was in python but I converted it to Javascript.

The algorithm used is made up of a function that finds the node with the least cost, and a while loop with some methods to update the graph's data structure. This implementation is fairly standard and is very similar to the many found online.

const processed = [];
const find_lowest_cost_node = (costs) => {
    lowest_cost = Infinity
    lowest_cost_node = null
    const costKeys = Object.keys(costs);
    costKeys.forEach((key, index) => {
      cost = costs[key];
      if (cost < lowest_cost && processed.indexOf(key) === -1){
        lowest_cost = cost;
        lowest_cost_node = key
      }
    });
   return lowest_cost_node;
}

let node = find_lowest_cost_node(costs);
while(node){
  const cost = costs[node];
  const neighbors = graph[node];
  const keys = Object.keys(neighbors);
  keys.forEach((key, index) => {
     const new_cost = cost + neighbors[key];
      if(costs[key] > new_cost){
        costs[key] = new_cost;
        parents[key] = node;
      }
   });
  processed.push(node);
  node = find_lowest_cost_node(costs)
}

The graph's data structure is made up of three hash tables : graph, costs and parents.

const graph = {};
graph['start'] = {};
graph['start']['a'] = 6;
graph['start']['b'] = 2;
graph['a'] = {};
graph['a']['fin'] = 7;
graph['b'] = {};
graph['b']['a'] = 3;
graph['b']['fin'] = 5;
graph['fin'] = {};

const costs = {};
costs['a'] = 6;
costs['b'] = 2;
costs['fin'] = Infinity;

const parents = {};
parents['a'] = 'start';
parents['b'] = 'start';
parents['fin'] = null;

As you use the application, it will build the hash tables, and once you have connected your final node you will be able to step though the process and view the algorithm's effect on them.

Watch this quick demo of how to use the application.

 

 

If you need more room for your graph, you can click the edit on codepen.

 

Please let me know if you find this useful or if you found any issues with it, either in the comments or contact me here.