In the last chapter we iterated over a simple graph using Bellman-Ford to find the shortest paths from a single vertex (our source) to all other vertices in the graph.

The complexity of Bellman-Ford is O(|V| E), which can approximate O(n^2) if every vertex has at least one outgoing edge. In other words: it's not terribly efficient.

Dijkstra's algorithm requires only one iteration, however and has a complexity of O(|V| log V), which is much more efficient.

As with Bellman-Ford, we'll use a directed, weighted graph with 6 vertices. In addition, we'll setup a memo table with our source S set to 0 and the rest of the vertices set to infinity.

There is a difference here, however, and it's critical! Dijkstra doesn't work with negative edge weights! I have adjusted this graph so that we don't have any negative weights, as you can see. Specifically the edges between S and E as well as C to B. In addition I've added a few edges to show that the algorithm will scale easily regardless of the number of edges involved.

//Dijkstra: Shortest path calculation//on an edge-weighted, directed graphclass MemoTable{  constructor(vertices){    this.S = {name: "S", cost: 0, visited: false};    this.table = [this.S];    for(var vertex of vertices){      this.table.push({name: vertex, cost: Number.POSITIVE_INFINITY, visited: false});    }  };  getCandidateVertices(){   return this.table.filter(entry => {     return entry.visited === false;   });  };  nextVertex(){   const candidates = this.getCandidateVertices();   if(candidates.length > 0){     return candidates.reduce((prev, curr) => {       return prev.cost < curr.cost ? prev : curr;     });   }else{     return null;   }  };  setCurrentCost(vertex, cost){    this.getEntry(vertex).cost =cost;  };  setAsVisited(vertex){    this.getEntry(vertex).visited = true;  };  getEntry(vertex){    return this.table.find(entry => entry.name == vertex);  };  getCost(vertex){    return this.getEntry(vertex).cost;  };  toString(){    console.log(this.table);  }};const vertices = ["A", "B","C", "D", "E"];const graph = [  {from : "S", to :"A", cost: 4},  {from : "S", to :"E", cost: 2},  {from : "A", to :"D", cost: 3},  {from : "A", to :"C", cost: 6},  {from : "A", to :"B", cost: 5},  {from : "B", to :"A", cost: 3},  {from : "C", to :"B", cost: 1},  {from : "D", to :"C", cost: 3},  {from : "D", to :"A", cost: 1},  {from : "E", to: "D", cost: 1}]const memo = new MemoTable(vertices);const evaluate = vertex => {  const edges = graph.filter(path => {    return path.from === vertex.name;  });  for(edge of edges){    const currentVertexCost = memo.getCost(edge.from);    const toVertexCost = memo.getCost(edge.to);    const tentativeCost = currentVertexCost + edge.cost;    if(tentativeCost < toVertexCost){      memo.setCurrentCost(edge.to, tentativeCost);    }  };  memo.setAsVisited(vertex.name);  const next = memo.nextVertex();  if(next) evaluate(next);}//kick it off from the source vertexevaluate(memo.S);memo.toString();