Graph Traversal: Dijkstra

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.

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