@algorithm.ts/bellman-ford

@algorithm.ts/bellman-ford

A typescript implementation of the bellman-ford algorithm.

The following definition is quoted from Wikipedia (https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm):

The Bellman–Ford algorithm is an algorithm that computes shortest paths from a single source vertex to all of the other vertices in a weighted digraph. It is slower than Dijkstra's algorithm for the same problem, but more versatile, as it is capable of handling graphs in which some of the edge weights are negative numbers. The algorithm was first proposed by Alfonso Shimbel (1955), but is instead named after Richard Bellman and Lester Ford Jr., who published it in 1958 and 1956, respectively. Edward F. Moore also published a variation of the algorithm in 1959, and for this reason it is also sometimes called the Bellman–Ford–Moore algorithm.

Install

• npm

  npm install --save @algorithm.ts/bellman-ford
  

• yarn

  yarn add @algorithm.ts/bellman-ford
  

Usage

• Simple

  import type { IGraph } from '@algorithm.ts/bellman-ford'
  import bellmanFord from '@algorithm.ts/bellman-ford'
  
  const graph: IGraph = {
    N: 4,
    source: 0,
    edges: [
      { to: 1, cost: 2 },
      { to: 2, cost: 2 },
      { to: 3, cost: 2 },
      { to: 3, cost: 1 },
    ],
    G: [[0], [1, 2], [3], []],
  }
  const dist: number[] = []
  bellmanFord(graph, { dist }) // => true, which means there is no negative-cycle.
  dist
  // => [0, 2, 4, 4]
  // 
  //    Which means:
  //      0 --> 0: cost is 0
  //      0 --> 1: cost is 2
  //      0 --> 2: cost is 4
  //      0 --> 3: cost is 4
  

• Options

  Name	Type	Required	Description
  INF	number	false	A big number, representing the unreachable cost.
  from	number[]	false	Record the shortest path parent source point to the specified point.
  dist	number[]	false	An array recording the shortest distance to the source point.
  inq	boolean	false	Used to check if an element is already in the queue.
  inqTimes	number[]	false	Record the number of times an element is enqueued, used to check whether there is a negative cycle.

Example

• Get shortest path.

  import bellmanFord from '@algorithm.ts/bellman-ford'
  
  const A = 0
  const B = 1
  const C = 2
  const D = 3
  
  const graph: IGraph = {
    N: 4,
    source: A,
    edges: [
      // Nodes: [A, B, C, D]
      { to: B, cost: 1 },       // A-B (1)
      { to: A, cost: -1 },      // B-A (-1)
      { to: C, cost: 0.87 },    // B-C (0.87)
      { to: B, cost: -0.87 },   // C-B (-0.87)
      { to: D, cost: 5 },       // C-D (5)
      { to: C, cost: -5 },      // D-C (-5)
    ],
    G: [[0], [1, 2], [3, 4], [5]],
  }
  
  const noNegativeCycle: boolean = bellmanFord(graph, undefined, context => {
    const a2aPath: number[] = context.getShortestPathTo(A)
    const a2bPath: number[] = context.getShortestPathTo(B)
    const a2cPath: number[] = context.getShortestPathTo(C)
    const a2dPath: number[] = context.getShortestPathTo(D)
  
    a2aPath // => [0]
    a2bPath // => [0, 1]
    a2cPath // => [0, 1, 2]
    a2dPath // => [0, 1, 2, 3]
  })
  

• A solution for leetcode "Number of Ways to Arrive at Destination" (https://leetcode.com/problems/number-of-ways-to-arrive-at-destination/):

  import type { IEdge, IGraph } from '@algorithm.ts/bellman-ford'
  import bellmanFord from '@algorithm.ts/bellman-ford'
  
  const MOD = 1e9 + 7
  export function countPaths(N: number, roads: number[][]): number {
    const edges: IEdge[] = []
    const G: number[][] = new Array(N)
    for (let i = 0; i < N; ++i) G[i] = []
    for (const [from, to, cost] of roads) {
      G[from].push(edges.length)
      edges.push({ to, cost })
  
      G[to].push(edges.length)
      edges.push({ to: from, cost })
    }
  
    const source = 0
    const target = N - 1
    const graph: IGraph = { N, source: target, edges, G }
    const dist: number[] = customDist ?? []
    bellmanFord.bellmanFord(graph, { INF: 1e12, dist })
  
    const dp: number[] = new Array(N).fill(-1)
    return dfs(source)
  
    function dfs(o: number): number {
      if (o === target) return 1
  
      let answer = dp[o]
      if (answer !== -1) return answer
  
      answer = 0
      const d = dist[o]
      for (const idx of G[o]) {
        const e: IEdge = edges[idx]
        if (dist[e.to] + e.cost === d) {
          const t = dfs(e.to)
          answer = modAdd(answer, t)
        }
      }
      return dp[o] = answer
    }
  }
  
  function modAdd(x: number, y: number): number {
    const z: number = x + y
    return z < MOD ? z : z - MOD
  }
  

Related

• 《算法竞赛入门经典（第2版）》（刘汝佳）： P363 Bellman-Ford 算法
• bellman-ford | Wikipedia
• @algorithm.ts/circular-queue