BellmanFord.js

/*
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 also detects negative weight cycle.

Complexity:
 Worst-case performance O(VE)
 Best-case performance O(E)
 Worst-case space complexity O(V)

Reference:
 https://en.wikipedia.org/wiki/Bellman–Ford_algorithm
 https://cp-algorithms.com/graph/bellman_ford.html

*/

/**
 *
 * @param graph Graph in the format (u, v, w) where
 * the edge is from vertex u to v. And weight
 * of the edge is w.
 * @param V Number of vertices in graph
 * @param E Number of edges in graph
 * @param src Starting node
 * @param dest Destination node
 * @returns Shortest distance from source to destination
 */
function BellmanFord(graph, V, E, src, dest) {
 // Initialize distance of all vertices as infinite.
 const dis = Array(V).fill(Infinity)
 // initialize distance of source as 0
 dis[src] = 0

 // Relax all edges |V| - 1 times. A simple
 // shortest path from src to any other
 // vertex can have at-most |V| - 1 edges
 for (let i = 0; i < V - 1; i++) {
 for (let j = 0; j < E; j++) {
 if (dis[graph[j][0]] + graph[j][2] < dis[graph[j][1]]) {
 dis[graph[j][1]] = dis[graph[j][0]] + graph[j][2]
 }
 }
 }
 // check for negative-weight cycles.
 for (let i = 0; i < E; i++) {
 const x = graph[i][0]
 const y = graph[i][1]
 const weight = graph[i][2]
 if (dis[x] !== Infinity && dis[x] + weight < dis[y]) {
 return null
 }
 }
 for (let i = 0; i < V; i++) {
 if (i === dest) return dis[i]
 }
}

export { BellmanFord }