Graph Traversal: Bellman Ford

One of the most fascinating uses of graphs is in the optimization of path traversal, which can be used in a vast number of calculations.

As mentioned in the previous chapter, graphs can be used to represent all kinds of information:

• A network of any kind. Social (friends) or digital (computers or the internet), for example
• A decision tree
• Contributions from members of any kind to a cause of any kind
• Atomic interactions in physics, chemistry or biology

Navigation between various endpoints - If you apply weighting to the edges or vertices, you can run useful calculations for just about anything. One of the most common is finding the shortest path between two vertices.

<span class="hljs-comment">//Bellman-Ford: Shortest path calculation</span>
<span class="hljs-comment">//on an edge-weighted, directed graph</span>
<span class="hljs-keyword">const</span> vertices = [<span class="hljs-string">&quot;S&quot;</span>, <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">var</span> memo = {
  <span class="hljs-attr">S</span>:<span class="hljs-number">0</span>,
  <span class="hljs-attr">A</span>:<span class="hljs-title class_">Number</span>.<span class="hljs-property">POSITIVE_INFINITY</span>,
  <span class="hljs-attr">B</span>:<span class="hljs-title class_">Number</span>.<span class="hljs-property">POSITIVE_INFINITY</span>,
  <span class="hljs-attr">C</span>:<span class="hljs-title class_">Number</span>.<span class="hljs-property">POSITIVE_INFINITY</span>,
  <span class="hljs-attr">D</span>:<span class="hljs-title class_">Number</span>.<span class="hljs-property">POSITIVE_INFINITY</span>,
  <span class="hljs-attr">E</span>:<span class="hljs-title class_">Number</span>.<span class="hljs-property">POSITIVE_INFINITY</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">5</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;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">2</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">10</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">8</span>}
];

<span class="hljs-keyword">const</span> <span class="hljs-title function_">iterate</span> = (<span class="hljs-params"></span>) =&gt; {
  <span class="hljs-keyword">var</span> doItAgain = <span class="hljs-literal">false</span>;
  <span class="hljs-keyword">for</span>(fromVertex <span class="hljs-keyword">of</span> vertices){
    <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> === fromVertex;
    });
    <span class="hljs-keyword">for</span>(edge <span class="hljs-keyword">of</span> edges){
      <span class="hljs-keyword">const</span> potentialCost = memo[edge.<span class="hljs-property">from</span>] + edge.<span class="hljs-property">cost</span>;
      <span class="hljs-keyword">if</span>(potentialCost &lt; memo[edge.<span class="hljs-property">to</span>]){
        memo[edge.<span class="hljs-property">to</span>] = potentialCost;
        doItAgain = <span class="hljs-literal">true</span>;
      }
    }
  }
  <span class="hljs-keyword">return</span> doItAgain;
}
<span class="hljs-keyword">for</span>(vertex <span class="hljs-keyword">of</span> vertices){
  <span class="hljs-keyword">if</span>(!<span class="hljs-title function_">iterate</span>()) <span class="hljs-keyword">break</span>;
}
<span class="hljs-variable language_">console</span>.<span class="hljs-title function_">log</span>(memo);