programming-examples/js/Algorithms/bellman-ford.js

/**
 * Bellman–Ford algorithm computes shortest paths from a single source
 * vertex to all of the other vertices in a weighted digraph
 * (negative weights allowed).<br><br>
 * Time complexity: O(|V||E|) where V and E are the number of
 * vertices and edges respectively.
 *
 * @example
 *
 * var BellmanFord =
 *    require('path-to-algorithms/src/graphs/shortest-path/bellman-ford');
 * var Edge = BellmanFord.Edge;
 * var bellmanFord = BellmanFord.bellmanFord;
 * var edges = [];
 * var vertexes = [
 *   new Vertex(0),
 *   new Vertex(1),
 *   new Vertex(2),
 *   new Vertex(3),
 *   new Vertex(4)
 * ];
 *
 * edges.push(new Edge(0, 1, -1));
 * edges.push(new Edge(0, 2, 4));
 * edges.push(new Edge(1, 2, 3));
 * edges.push(new Edge(1, 3, 2));
 * edges.push(new Edge(3, 1, 1));
 * edges.push(new Edge(4, 3, -3));
 * edges.push(new Edge(1, 4, 2));
 * edges.push(new Edge(3, 2, 5));
 *
 * // {
 * //   parents:   { '0': null, '1':  0, '2': 1, '3':  4, '4': 1 },
 * //   distances: { '0': 0,    '1': -1, '2': 2, '3': -2, '4': 1 }
 * // }
 * var pathInfo = bellmanFord(vertexes, edges, 0);
 *
 * @module graphs/shortest-path/bellman-ford
 */
(function (exports) {

  'use strict';

  exports.Vertex = require('../../data-structures/vertex').Vertex;
  exports.Edge = require('../../data-structures/edge').Edge;

  /**
   * Computes shortest paths from a single source
   * vertex to all of the other vertices.
   *
   * @public
   * @param {Array} vertexes Vertices of the graph.
   * @param {Array} edges Edges of the graph.
   * @param {Number} source Start vertex.
   * @returns {Object} Object with two arrays (parents and distances)
   *   with shortest-path information or undefined if the graph
   *   has a negative cycle.
   */
  exports.bellmanFord = function (vertexes, edges, source) {
    var distances = {};
    var parents = {};
    var c;
    if (source) {
      for (var i = 0; i < vertexes.length; i += 1) {
        distances[vertexes[i].id] = Infinity;
        parents[vertexes[i].id] = null;
      }
      distances[source.id] = 0;
      for (i = 0; i < vertexes.length - 1; i += 1) {
        for (var j = 0; j < edges.length; j += 1) {
          c = edges[j];
          if (distances[c.from.id] + c.distance < distances[c.to.id]) {
            distances[c.to.id] = distances[c.from.id] + c.distance;
            parents[c.to.id] = c.from.id;
          }
        }
      }

      for (i = 0; i < edges.length; i += 1) {
        c = edges[i];
        if (distances[c.from.id] + c.distance < distances[c.to.id]) {
          return undefined;
        }
      }
    }

    return { parents: parents, distances: distances };
  };

})(typeof window === 'undefined' ? module.exports : window);