Skip to content

Commit 8a263e6

Browse files
author
duaraghav8@gmail
committed
Bellman Ford Shortest Path
1 parent 2421d79 commit 8a263e6

File tree

5 files changed

+120
-1
lines changed

5 files changed

+120
-1
lines changed

‎algorithm/category.json

+2-1
Original file line numberDiff line numberDiff line change
@@ -3,7 +3,8 @@
33
"name": "Graph Search",
44
"list": {
55
"dfs": "DFS",
6-
"bfs": "BFS"
6+
"bfs": "BFS",
7+
"bellman_ford": "BELLMAN_FORD"
78
}
89
},
910
"search": {

‎algorithm/graph_search/bellman_ford/desc.json

+16
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,16 @@
1+
{
2+
"BELLMAN_FORD": "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 is different from Dijksstra's Shortest Path Algorithm becuase it allows NEGATIVE weights unlike Dijkstra's.",
3+
"Applications": [
4+
"Packet Routing - A variation of BF is used in the Distance vector Routing Protocol"
5+
],
6+
"Complexity": {
7+
"time": "worst O(|V|.|E|)",
8+
"space": "worst O(|V|)"
9+
},
10+
"References": [
11+
"<a href='https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm'>Wikipedia</a>"
12+
],
13+
"files": {
14+
"shortest_path": "Finding the shortest path"
15+
}
16+
}

‎algorithm/graph_search/bellman_ford/shortest_path/code.js

+80
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,80 @@
1+
function BELLMAN_FORD (src, dest) {
2+
var weights = new Array (G.length);
3+
4+
for (var i = 0; i < G.length; i++) {
5+
weights [i] = MAX_VALUE;
6+
tracer._weight (i, MAX_VALUE);
7+
}
8+
weights [src] = 0;
9+
tracer._weight (src, 0);
10+
11+
tracer._print ('Initializing weights to: [' + weights + ']');
12+
tracer._print ('');
13+
14+
//begin BF algorithm execution
15+
i = G.length - 1;
16+
while (i--) {
17+
tracer._print ('Iteration: ' + (G.length - i - 1));
18+
tracer._print ('------------------------------------------------------------------');
19+
20+
for (var currentNode = 0; currentNode < G.length; currentNode++) {
21+
for (var currentNodeNeighbor = 0; currentNodeNeighbor <= G.length; currentNodeNeighbor++) {
22+
if (G [currentNode] [currentNodeNeighbor]) { //proceed to relax Edges only if a particular weight != 0 (0 represents no edge)
23+
tracer._print ('Exploring edge from ' + currentNode + ' to ' + currentNodeNeighbor + ', weight = ' + G [currentNode] [currentNodeNeighbor]);
24+
tracer._visit (currentNodeNeighbor, currentNode, undefined);
25+
26+
if ( weights [currentNodeNeighbor] > (weights [currentNode] + G [currentNode] [currentNodeNeighbor]) ) {
27+
weights [currentNodeNeighbor] = weights [currentNode] + G [currentNode] [currentNodeNeighbor];
28+
tracer._print ('weights [' + currentNodeNeighbor + '] = weights [' + currentNode + '] + ' + G [currentNode] [currentNodeNeighbor]);
29+
}
30+
31+
tracer._leave (currentNodeNeighbor, currentNode, undefined);
32+
}
33+
}
34+
}
35+
36+
tracer._print ('updated weights: [' + weights + ']');
37+
tracer._print ('');
38+
}
39+
40+
//check for cycle
41+
for (currentNode = 0; currentNode < G.length; currentNode++) {
42+
for (currentNodeNeighbor = 0; currentNodeNeighbor <= G.length; currentNodeNeighbor++) {
43+
if (G [currentNode] [currentNodeNeighbor]) {
44+
if ( weights [currentNodeNeighbor] > (weights [currentNode] + G [currentNode] [currentNodeNeighbor]) ) {
45+
return (MAX_VALUE);
46+
}
47+
}
48+
}
49+
}
50+
51+
tracer._print ('Final weights for the source ' + src + ' are: [' + weights + ']');
52+
53+
return weights [dest];
54+
}
55+
56+
var src = Math.random() * G.length | 0, dest;
57+
var MAX_VALUE = Infinity;
58+
var minWeight;
59+
60+
/*
61+
src = start node
62+
dest = start node (but will eventually at as the end node)
63+
*/
64+
65+
do {
66+
dest = Math.random() * G.length | 0;
67+
}
68+
while (src === dest);
69+
70+
tracer._pace(100);
71+
tracer._print('finding the shortest path from ' + src + ' to ' + dest);
72+
tracer._sleep(1000);
73+
74+
minWeight = BELLMAN_FORD (src, dest);
75+
76+
if (minWeight === MAX_VALUE) {
77+
tracer._print('there is no path from ' + src + ' to ' + dest);
78+
} else {
79+
tracer._print('the shortest path from ' + src + ' to ' + dest + ' is ' + minWeight);
80+
}

‎algorithm/graph_search/bellman_ford/shortest_path/data.js

+11
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,11 @@
1+
var tracer = new DirectedGraphTracer();
2+
//var G = WeightedGraph.random( (Math.random () * 10) | 0, .3, -9, 9);
3+
var G = [
4+
[0,-1,4,0,0],
5+
[0,0,3,2,2],
6+
[0,0,0,0,0],
7+
[0, 1,5,0,0],
8+
[0,0,0,-3,0]
9+
];
10+
11+
tracer._setData(G);

‎server.js

+11
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,11 @@
1+
process.chdir (__dirname);
2+
3+
var express = require ('express'),
4+
serveStatic = require ('serve-static'),
5+
app = express ();
6+
7+
app
8+
.use (serveStatic (__dirname))
9+
.listen (8080, function () {
10+
console.log ('ready');
11+
});

0 commit comments

Comments
 (0)