Files
JavaScript/Graphs/BellmanFord.js
Roland Hummel 86d333ee94 feat: Test running overhaul, switch to Prettier & reformat everything (#1407)
* chore: Switch to Node 20 + Vitest

* chore: migrate to vitest mock functions

* chore: code style (switch to prettier)

* test: re-enable long-running test

Seems the switch to Node 20 and Vitest has vastly improved the code's and / or the test's runtime!

see #1193

* chore: code style

* chore: fix failing tests

* Updated Documentation in README.md

* Update contribution guidelines to state usage of Prettier

* fix: set prettier printWidth back to 80

* chore: apply updated code style automatically

* fix: set prettier line endings to lf again

* chore: apply updated code style automatically

---------

Co-authored-by: github-actions <${GITHUB_ACTOR}@users.noreply.github.com>
Co-authored-by: Lars Müller <34514239+appgurueu@users.noreply.github.com>
2023-10-04 02:38:19 +05:30

59 lines
1.6 KiB
JavaScript
Raw Permalink Blame History

This file contains ambiguous Unicode characters

This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.

/*
The BellmanFord 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/BellmanFord_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 }