Last active
October 5, 2019 19:47
-
-
Save neenjaw/e83c32f57c6a2415c61158a828e6e961 to your computer and use it in GitHub Desktop.
Bellman Ford Visualization - https://colorlatte.com/article/visualize-the-bellmanford-algorithm-with-javascript
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
Initiate | |
distance - stores the distance of the shortest path from source to each vertex. | |
predecessor - for each vertex, predecessor stores its previous vertex on the path from the source to it. | |
For the object distance, define each property for the corresponding vertex as Infinity, except for the source, | |
which should be zero. For the object predecessor, set the property for every vertex as null. | |
Cycle | |
Repeatedly check all the edges to see if the stored distance (total weight from the source to a target vertex) | |
for side u of the edge plus the edge's weight w is smaller than the distance of another vertex u. | |
If it is true, set the distance of v as the distance of u plus w; and set predecessor of v as u. | |
The process repeats with vertices.length times to guarantee the shortest result. | |
Check | |
Do one more time and throw an error if there exists a negative-weight cycle. | |
The negative cycle is a problem because it prevents the algorithm from finding the correct answer. | |
*/ | |
export const graph = { | |
vertices: [ 'A', 'B', 'C', 'D', 'E' ], | |
edges: [ | |
{ u: 'A', v: 'B', w: 4 }, | |
{ u: 'A', v: 'C', w: 2 }, | |
{ u: 'B', v: 'C', w: 3 }, | |
{ u: 'B', v: 'D', w: 2 }, | |
{ u: 'B', v: 'E', w: 3 }, | |
{ u: 'C', v: 'B', w: 1 }, | |
{ u: 'C', v: 'D', w: 4 }, | |
{ u: 'C', v: 'E', w: 5 }, | |
{ u: 'E', v: 'D', w: -5 } | |
], | |
positions: { | |
A: { x: 60, y: 180 }, | |
B: { x: 240, y: 60 }, | |
C: { x: 240, y: 300 }, | |
D: { x: 420, y: 60 }, | |
E: { x: 420, y: 300 } | |
} | |
}; | |
export const bellmanFord = ({ vertices, edges }, source) => { | |
const distance = vertices.reduce((r, i) => ({ [i]: Infinity, ...r }), { [source]: 0 }); | |
const predecessor = vertices.reduce((r, i) => ({ [i]: null, ...r }), {}); | |
vertices.forEach(() => { | |
edges.forEach(({ u, v, w }) => { | |
if (distance[v] > distance[u] + w) { | |
distance[v] = distance[u] + w; | |
predecessor[v] = u; | |
} | |
}); | |
}); | |
// check for negative-weight cycles | |
for (let { u, v, w } of edges) { | |
if (distance[v] > distance[u] + w) throw 'Graph contains a negative-weight cycle'; | |
} | |
return { distance, predecessor }; | |
}; |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import { graph, bellmanFord } from './bellman'; | |
export const draw = () => { | |
const { distance, predecessor } = bellmanFord(graph, 'A'); | |
console.log({ distance, predecessor }); | |
}; |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import { draw } from './draw'; | |
draw(); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment