forked from mberktas/javascript-algorithms
-
Notifications
You must be signed in to change notification settings - Fork 0
/
bellmanFord.js
45 lines (41 loc) · 1.5 KB
/
bellmanFord.js
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
/**
* @param {Graph} graph
* @param {GraphVertex} startVertex
* @return {{distances, previousVertices}}
*/
export default function bellmanFord(graph, startVertex) {
const distances = {};
const previousVertices = {};
// Init all distances with infinity assuming that currently we can't reach
// any of the vertices except start one.
distances[startVertex.getKey()] = 0;
graph.getAllVertices().forEach((vertex) => {
previousVertices[vertex.getKey()] = null;
if (vertex.getKey() !== startVertex.getKey()) {
distances[vertex.getKey()] = Infinity;
}
});
// We need (|V| - 1) iterations.
for (let iteration = 0; iteration < (graph.getAllVertices().length - 1); iteration += 1) {
// During each iteration go through all vertices.
Object.keys(distances).forEach((vertexKey) => {
const vertex = graph.getVertexByKey(vertexKey);
// Go through all vertex edges.
graph.getNeighbors(vertex).forEach((neighbor) => {
const edge = graph.findEdge(vertex, neighbor);
// Find out if the distance to the neighbor is shorter in this iteration
// then in previous one.
const distanceToVertex = distances[vertex.getKey()];
const distanceToNeighbor = distanceToVertex + edge.weight;
if (distanceToNeighbor < distances[neighbor.getKey()]) {
distances[neighbor.getKey()] = distanceToNeighbor;
previousVertices[neighbor.getKey()] = vertex;
}
});
});
}
return {
distances,
previousVertices,
};
}