mirror of
https://github.com/TheAlgorithms/JavaScript.git
synced 2025-07-05 00:01:37 +08:00

* 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>
59 lines
1.6 KiB
JavaScript
59 lines
1.6 KiB
JavaScript
/*
|
||
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 }
|