Skip to content

Commit 65d0b1e

Browse files
64json64json
committed
few examples: change initial max value to infinity
1 parent dface42 commit 65d0b1e

File tree

5 files changed

+72
-70
lines changed

5 files changed

+72
-70
lines changed

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

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -27,7 +27,7 @@ var e; // e = start node
2727
do {
2828
e = Math.random() * G.length | 0;
2929
} while (s == e);
30-
var MAX_VALUE = 999;
30+
var MAX_VALUE = Infinity;
3131
tracer._pace(100);
3232
tracer._print('finding the shortest path from ' + s + ' to ' + e);
3333
tracer._sleep(1000);

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

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -25,7 +25,7 @@ var e; // e = end node
2525
do {
2626
e = Math.random() * G.length | 0;
2727
} while (s == e);
28-
var MAX_VALUE = 999;
28+
var MAX_VALUE = Infinity;
2929
var minWeight = MAX_VALUE;
3030
tracer._pace(100);
3131
tracer._print('finding the shortest path from ' + s + ' to ' + e);

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

Lines changed: 40 additions & 39 deletions
Original file line numberDiff line numberDiff line change
@@ -1,42 +1,43 @@
1-
function Dijkstra(start, end){
2-
tracer._sleep(333)
3-
var minIndex, minDistance;
4-
var S = []; // S[i] returns the distance from node v to node start
5-
var D = []; // D[i] indicates whether the i-th node is discovered or not
6-
for (var i = 0; i < G.length; i++){
7-
D.push(false);
8-
S[i] = 19990719 // Some big distance (infinity)
9-
}
10-
S[start] = 0; // Starting node is at distance 0 from itself
11-
for(var k = 0; k < G.length; k++){
12-
// Finding a node with the shortest distance from S[minIndex]
13-
minDistance = 19990719 // Some big distance (infinity)
14-
for(i = 0; i < G.length; i++){
15-
if(S[i] < minDistance && !D[i]){
16-
minDistance = S[i];
17-
minIndex = i;
18-
}
19-
}
20-
tracer._visit(minIndex,undefined);
21-
tracer._sleep(500);
22-
D[minIndex] = true;
23-
if(minDistance == 19990719){ // If the distance is big (infinity), there is no more paths
24-
tracer._print('there is no path from ' + s + ' to ' + e);
25-
return false;
26-
}
27-
// For every unvisited neighbour of current node, we check
28-
// whether the path to it is shorter if going over the current node
29-
for(i = 0; i < G.length; i++){
30-
if (G[minIndex][i] && !D[i] && ( S[i] > S[minIndex] + G[minIndex][i])){
31-
S[i] = S[minIndex] + G[minIndex][i];
32-
tracer._visit(i,minIndex,S[i]);
33-
tracer._sleep(500);
34-
tracer._leave(i,minIndex,S[i]);
35-
}
36-
}
37-
tracer._leave(minIndex,undefined);
38-
}
39-
tracer._print('the shortest path from ' + s + ' to ' + e + ' is ' + S[e]);
1+
function Dijkstra(start, end) {
2+
tracer._sleep(333);
3+
var MAX_VALUE = Infinity;
4+
var minIndex, minDistance;
5+
var S = []; // S[i] returns the distance from node v to node start
6+
var D = []; // D[i] indicates whether the i-th node is discovered or not
7+
for (var i = 0; i < G.length; i++) {
8+
D.push(false);
9+
S[i] = MAX_VALUE;
10+
}
11+
S[start] = 0; // Starting node is at distance 0 from itself
12+
for (var k = 0; k < G.length; k++) {
13+
// Finding a node with the shortest distance from S[minIndex]
14+
minDistance = MAX_VALUE;
15+
for (i = 0; i < G.length; i++) {
16+
if (S[i] < minDistance && !D[i]) {
17+
minDistance = S[i];
18+
minIndex = i;
19+
}
20+
}
21+
tracer._visit(minIndex, undefined);
22+
tracer._sleep(500);
23+
D[minIndex] = true;
24+
if (minDistance == MAX_VALUE) { // If the distance is infinity, there is no more paths
25+
tracer._print('there is no path from ' + s + ' to ' + e);
26+
return false;
27+
}
28+
// For every unvisited neighbour of current node, we check
29+
// whether the path to it is shorter if going over the current node
30+
for (i = 0; i < G.length; i++) {
31+
if (G[minIndex][i] && !D[i] && ( S[i] > S[minIndex] + G[minIndex][i])) {
32+
S[i] = S[minIndex] + G[minIndex][i];
33+
tracer._visit(i, minIndex, S[i]);
34+
tracer._sleep(500);
35+
tracer._leave(i, minIndex, S[i]);
36+
}
37+
}
38+
tracer._leave(minIndex, undefined);
39+
}
40+
tracer._print('the shortest path from ' + s + ' to ' + e + ' is ' + S[e]);
4041
}
4142

4243
var s = Math.random() * G.length | 0; // s = start node

‎algorithm/graph_search/floyd_warshall/shortest_paths/code.js‎

Lines changed: 29 additions & 28 deletions
Original file line numberDiff line numberDiff line change
@@ -1,34 +1,35 @@
1-
function FloydWarshall(){
2-
// Finds the shortest path between all nodes
3-
var S = new Array(G.length);
4-
for (var i = 0; i < G.length; i++) S[i] = new Array(G.length)
5-
for (i = 0; i < G.length; i++){
6-
tracer._visit(i)
7-
for (var j = 0; j < G.length; j++){
8-
// Distance to self is always 0
9-
if (i==j) S[i][i] = 0;
10-
// Distance between connected nodes is their weight
11-
else if (G[i][j] > 0){
12-
S[i][j] = G[i][j];
13-
tracer._visit(j,i,S[i][j]);
14-
tracer._leave(j,i,S[i][j]);
15-
}// Else we don't know the distnace and we set it to a big value (infinity)
16-
else S[i][j] = 19990719;
1+
function FloydWarshall() {
2+
// Finds the shortest path between all nodes
3+
var S = new Array(G.length);
4+
for (var i = 0; i < G.length; i++) S[i] = new Array(G.length)
5+
for (i = 0; i < G.length; i++) {
6+
tracer._visit(i)
7+
for (var j = 0; j < G.length; j++) {
8+
// Distance to self is always 0
9+
if (i == j) S[i][i] = 0;
10+
// Distance between connected nodes is their weight
11+
else if (G[i][j] > 0) {
12+
S[i][j] = G[i][j];
13+
tracer._visit(j, i, S[i][j]);
14+
tracer._leave(j, i, S[i][j]);
15+
}// Else we don't know the distance and we set it to infinity
16+
else S[i][j] = MAX_VALUE;
17+
}
18+
tracer._leave(i)
1719
}
18-
tracer._leave(i)
19-
}
20-
// If there is a shorter path using k, use it instead
21-
for (var k = 0; k < G.length; k++)
22-
for (i = 0; i < G.length; i++)
20+
// If there is a shorter path using k, use it instead
21+
for (var k = 0; k < G.length; k++)
22+
for (i = 0; i < G.length; i++)
23+
for (j = 0; j < G.length; j++)
24+
if (S[i][j] > S[i][k] + S[k][j])
25+
S[i][j] = S[i][k] + S[k][j];
26+
for (i = 0; i < G.length; i++)
2327
for (j = 0; j < G.length; j++)
24-
if (S[i][j] > S[i][k] + S[k][j])
25-
S[i][j] = S[i][k] + S[k][j];
26-
for (i = 0; i < G.length; i++)
27-
for (j = 0; j < G.length; j++)
28-
if(S[i][j] == 19990719) tracer._print('there is no path from ' + i + ' to ' + j);
29-
else tracer._print('the shortest path from ' + i +
30-
' to ' + j + ' is ' + S[i][j]);
28+
if (S[i][j] == MAX_VALUE) tracer._print('there is no path from ' + i + ' to ' + j);
29+
else tracer._print('the shortest path from ' + i +
30+
' to ' + j + ' is ' + S[i][j]);
3131
}
32+
var MAX_VALUE = Infinity;
3233
tracer._pace(200);
3334
tracer._print('finding the shortest paths from and to all nodes');
3435
FloydWarshall();

‎algorithm/sorting/merge/basic/code.js‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -59,7 +59,7 @@ mergeSort.merge = function(start, middle, end) {
5959
i++;
6060
}
6161

62-
tempArray = [];
62+
var tempArray = [];
6363
for (i = start; i < end; i++) tempArray.push(D[i]);
6464
tracer._print('merged array = [' + tempArray.join(', ') + ']');
6565
};

0 commit comments

Comments
 (0)