Skip to content

Commit d656bed

Browse files
64json64json
committed
add "shortest_path" in "DFS"
1 parent cd98310 commit d656bed

File tree

11 files changed

+89
-40
lines changed

11 files changed

+89
-40
lines changed

algorithm/graph_search/dfs/sample2/code.js renamed to algorithm/graph_search/dfs/all_paths/code.js

File renamed without changes.

algorithm/graph_search/dfs/sample2/data.js renamed to algorithm/graph_search/dfs/all_paths/data.js

File renamed without changes.

algorithm/graph_search/dfs/sample1/code.js renamed to algorithm/graph_search/dfs/basic/code.js

File renamed without changes.

algorithm/graph_search/dfs/sample1/data.js renamed to algorithm/graph_search/dfs/basic/data.js

File renamed without changes.

‎algorithm/graph_search/dfs/config.json‎

Lines changed: 4 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -21,8 +21,9 @@
2121
"https://en.wikipedia.org/wiki/Depth-first_search"
2222
],
2323
"files": {
24-
"sample1": "Visiting all connected nodes without making any circuit",
25-
"sample2": "Going through all paths without making any circuit",
26-
"sample3": "DFS of Weighted Graph"
24+
"basic": "Visiting all connected nodes without making any circuit",
25+
"all_paths": "Going through all paths without making any circuit",
26+
"weighted_graph": "DFS of Weighted Graph",
27+
"shortest_path": "Finding the shortest path"
2728
}
2829
}

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

Lines changed: 0 additions & 36 deletions
This file was deleted.

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

Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
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+
9+
function DFS(node, parent, weight) { // node = current node, parent = previous node
10+
if (minWeight < weight) return;
11+
if (node == e) {
12+
tracer._visit(node, parent, weight);
13+
tracer._leave(node, parent, 0);
14+
if (minWeight > weight) {
15+
minWeight = weight;
16+
}
17+
return;
18+
}
19+
D[node] = true; // label current node as discovered
20+
tracer._visit(node, parent, weight);
21+
for (var i = 0; i < G[node].length; i++) {
22+
if (G[node][i]) { // if the path from current node to the i-th node exists
23+
if (!D[i]) { // if the i-th node is not labeled as discovered
24+
DFS(i, node, weight + G[node][i]); // recursively call DFS
25+
}
26+
}
27+
}
28+
D[node] = false; // label current node as undiscovered
29+
tracer._leave(node, parent, 0);
30+
}
31+
32+
tracer._pace(100);
33+
tracer._print('finding the shortest path from ' + s + ' to ' + e);
34+
tracer._sleep(1000);
35+
D = [];
36+
for (var i = 0; i < G.length; i++) D[i] = false;
37+
DFS(s, undefined, 0);
38+
if (minWeight == Number.MAX_VALUE) {
39+
tracer._print('there is no path from ' + s + ' to ' + e);
40+
} else {
41+
tracer._print('the shortest path from ' + s + ' to ' + e + ' is ' + minWeight);
42+
}

‎algorithm/graph_search/dfs/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/weighted_graph/code.js‎

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
var D; // D[i] indicates whether the i-th node is discovered or not
2+
3+
function DFS(node, parent, weight) { // node = current node, parent = previous node
4+
D[node] = true; // label current node as discovered
5+
tracer._visit(node, parent, weight);
6+
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
8+
if (!D[i]) { // if the i-th node is not labeled as discovered
9+
DFS(i, node, weight + G[node][i]); // recursively call DFS
10+
}
11+
}
12+
}
13+
D[node] = false; // label current node as undiscovered
14+
tracer._leave(node, parent, 0);
15+
}
16+
17+
tracer._pace(1000);
18+
for (var i = 0; i < G.length; i++) { // start from every node
19+
tracer._print('start from ' + i);
20+
D = [];
21+
for (var j = 0; j < G.length; j++) D[j] = false;
22+
DFS(i, undefined, 0);
23+
tracer._clear();
24+
}

algorithm/graph_search/dfs/sample3/data.js renamed to algorithm/graph_search/dfs/weighted_graph/data.js

File renamed without changes.

0 commit comments

Comments
 (0)