Repository navigation
Expand file tree
/
Copy pathBellmanFord.js
More file actions
58 lines (52 loc) · 1.6 KB
/
Copy pathBellmanFord.js
File metadata and controls
58 lines (52 loc) · 1.6 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
/*
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 }