Skip to content

Commit bf10c89

Browse files
64json64json
committed
add "shortest_path" in "bfs"
1 parent fcdf78e commit bf10c89

File tree

8 files changed

+79
-27
lines changed

8 files changed

+79
-27
lines changed

‎algorithm/graph_search/bfs/basic/code.js‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,13 +1,13 @@
11
function BFS(s) { // s = start node
22
var Q = [];
3-
tracer._visit(s);
43
Q.push(s); // add start node to queue
4+
tracer._visit(s);
55
while (Q.length > 0) {
66
var node = Q.shift(); // dequeue
77
for (var i = 0; i < G[node].length; i++) {
88
if (G[node][i]) { // if current node has the i-th node as a child
9-
tracer._visit(i, node);
109
Q.push(i); // add child node to queue
10+
tracer._visit(i, node);
1111
}
1212
}
1313
}

‎algorithm/graph_search/bfs/config.json‎

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -17,6 +17,7 @@
1717
"https://en.wikipedia.org/wiki/Breadth-first_search"
1818
],
1919
"files": {
20-
"basic": "Searching a tree"
20+
"basic": "Searching a tree",
21+
"shortest_path": "Finding the shortest path"
2122
}
2223
}

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

Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
function BFS() {
2+
var W = []; // W[i] indicates the length of the shortest path from start node to the i-th node
3+
var Q = [];
4+
for (var i = 0; i < G.length; i++) {
5+
W.push(MAX_VALUE);
6+
tracer._weight(i, MAX_VALUE);
7+
}
8+
W[s] = 0;
9+
Q.push(s); // add start node to queue
10+
tracer._visit(s, undefined, 0);
11+
while (Q.length > 0) {
12+
var node = Q.shift(); // dequeue
13+
for (var i = 0; i < G[node].length; i++) {
14+
if (G[node][i]) { // if the edge from current node to the i-th node exists
15+
if (W[i] > W[node] + G[node][i]) { // if current path is shorter than the previously shortest path
16+
W[i] = W[node] + G[node][i]; // update the length of the shortest path
17+
Q.push(i); // add child node to queue
18+
tracer._visit(i, node, W[i]);
19+
}
20+
}
21+
}
22+
}
23+
return W[e];
24+
}
25+
26+
var s = Math.random() * G.length | 0; // s = start node
27+
var e; // e = start node
28+
do {
29+
e = Math.random() * G.length | 0;
30+
} while (s == e);
31+
var MAX_VALUE = 999;
32+
tracer._pace(500);
33+
tracer._print('finding the shortest path from ' + s + ' to ' + e);
34+
tracer._sleep(1000);
35+
var minWeight = BFS(s);
36+
if (minWeight == MAX_VALUE) {
37+
tracer._print('there is no path from ' + s + ' to ' + e);
38+
} else {
39+
tracer._print('the shortest path from ' + s + ' to ' + e + ' is ' + minWeight);
40+
}

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

Lines changed: 10 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,10 @@
1+
var tracer = new WeightedGraphTracer();
2+
/*var G = [ // G[i][j] indicates the weight of the path from the i-th node to the j-th node
3+
[0, 3, 0, 1, 0],
4+
[5, 0, 1, 2, 4],
5+
[1, 0, 0, 2, 0],
6+
[0, 2, 0, 0, 1],
7+
[0, 1, 3, 0, 0]
8+
];*/
9+
var G = tracer.createRandomData(10, .3, 1, 9);
10+
tracer.setData(G);

‎algorithm/graph_search/dfs/all_paths/code.js‎

Lines changed: 3 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -1,10 +1,8 @@
1-
var D; // D[i] indicates whether the i-th node is discovered or not
2-
31
function DFS(node, parent) { // node = current node, parent = previous node
42
D[node] = true; // label current node as discovered
53
tracer._visit(node, parent);
64
for (var i = 0; i < G[node].length; i++) {
7-
if (G[node][i]) { // if the path from current node to the i-th node exists
5+
if (G[node][i]) { // if the edge from current node to the i-th node exists
86
if (!D[i]) { // if the i-th node is not labeled as discovered
97
DFS(i, node); // recursively call DFS
108
}
@@ -14,10 +12,11 @@ function DFS(node, parent) { // node = current node, parent = previous node
1412
tracer._leave(node, parent);
1513
}
1614

15+
var D; // D[i] indicates whether the i-th node is discovered or not
1716
for (var i = 0; i < G.length; i++) { // start from every node
1817
tracer._print('start from ' + i);
1918
D = [];
20-
for (var j = 0; j < G.length; j++) D[j] = false;
19+
for (var j = 0; j < G.length; j++) D.push(false);
2120
DFS(i);
2221
tracer._clear();
2322
}

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

Lines changed: 11 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -1,11 +1,3 @@
1-
var D = []; // D[i] indicates whether the i-th node is discovered or not
2-
var s = Math.random() * G.length | 0;
3-
var e;
4-
do {
5-
e = Math.random() * G.length | 0;
6-
} while (s == e);
7-
var minWeight = Number.MAX_VALUE;
8-
91
function DFS(node, parent, weight) { // node = current node, parent = previous node
102
if (minWeight < weight) return;
113
if (node == e) {
@@ -29,13 +21,20 @@ function DFS(node, parent, weight) { // node = current node, parent = previous n
2921
tracer._leave(node, parent, 0);
3022
}
3123

32-
tracer._pace(100);
24+
var s = Math.random() * G.length | 0; // s = start node
25+
var e; // e = end node
26+
do {
27+
e = Math.random() * G.length | 0;
28+
} while (s == e);
29+
var MAX_VALUE = 999;
30+
var minWeight = MAX_VALUE;
31+
tracer._pace(500);
3332
tracer._print('finding the shortest path from ' + s + ' to ' + e);
3433
tracer._sleep(1000);
35-
D = [];
36-
for (var i = 0; i < G.length; i++) D[i] = false;
34+
var D = []; // D[i] indicates whether the i-th node is discovered or not
35+
for (var i = 0; i < G.length; i++) D.push(false);
3736
DFS(s, undefined, 0);
38-
if (minWeight == Number.MAX_VALUE) {
37+
if (minWeight == MAX_VALUE) {
3938
tracer._print('there is no path from ' + s + ' to ' + e);
4039
} else {
4140
tracer._print('the shortest path from ' + s + ' to ' + e + ' is ' + minWeight);

‎algorithm/graph_search/dfs/weighted_graph/code.js‎

Lines changed: 3 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -1,10 +1,8 @@
1-
var D; // D[i] indicates whether the i-th node is discovered or not
2-
31
function DFS(node, parent, weight) { // node = current node, parent = previous node
42
D[node] = true; // label current node as discovered
53
tracer._visit(node, parent, weight);
64
for (var i = 0; i < G[node].length; i++) {
7-
if (G[node][i]) { // if the path from current node to the i-th node exists
5+
if (G[node][i]) { // if the edge from current node to the i-th node exists
86
if (!D[i]) { // if the i-th node is not labeled as discovered
97
DFS(i, node, weight + G[node][i]); // recursively call DFS
108
}
@@ -14,11 +12,12 @@ function DFS(node, parent, weight) { // node = current node, parent = previous n
1412
tracer._leave(node, parent, 0);
1513
}
1614

15+
var D; // D[i] indicates whether the i-th node is discovered or not
1716
tracer._pace(1000);
1817
for (var i = 0; i < G.length; i++) { // start from every node
1918
tracer._print('start from ' + i);
2019
D = [];
21-
for (var j = 0; j < G.length; j++) D[j] = false;
20+
for (var j = 0; j < G.length; j++) D.push(false);
2221
DFS(i, undefined, 0);
2322
tracer._clear();
2423
}

‎js/module/weighted_graph.js‎

Lines changed: 8 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -87,6 +87,10 @@ WeightedGraphTracer.prototype.setData = function (G) {
8787
this.refresh();
8888
};
8989

90+
GraphTracer.prototype._weight = function (target, weight, delay) {
91+
this.pushStep({type: 'weight', target: target, weight: weight}, delay);
92+
};
93+
9094
GraphTracer.prototype._visit = function (target, source, weight) {
9195
this.pushStep({type: 'visit', target: target, source: source, weight: weight}, true);
9296
};
@@ -99,6 +103,10 @@ GraphTracer.prototype._leave = function (target, source, weight) {
99103
WeightedGraphTracer.prototype.processStep = function (step, options) {
100104
console.log(step);
101105
switch (step.type) {
106+
case 'weight':
107+
var targetNode = graph.nodes(n(step.target));
108+
if (step.weight !== undefined) targetNode.weight = step.weight;
109+
break;
102110
case 'visit':
103111
case 'leave':
104112
var visit = step.type == 'visit';
@@ -116,10 +124,6 @@ WeightedGraphTracer.prototype.processStep = function (step, options) {
116124
if (source === undefined) source = '';
117125
printTrace(visit ? source + ' -> ' + step.target : source + ' <- ' + step.target);
118126
break;
119-
case 'weight':
120-
var targetNode = graph.nodes(n(step.target));
121-
targetNode.weight = step.weight;
122-
break;
123127
default:
124128
GraphTracer.prototype.processStep.call(this, step, options);
125129
}

0 commit comments

Comments
 (0)