Skip to content

Commit 85696a3

Browse files
64json64json
committed
Merge branch 'gh-pages' of https://github.com/parkjs814/AlgorithmVisualizer into gh-pages
2 parents 49b91a0 + 6f1b998 commit 85696a3

File tree

6 files changed

+112
-54
lines changed

6 files changed

+112
-54
lines changed

‎algorithm/category.json

+2-1
Original file line numberDiff line numberDiff line change
@@ -5,7 +5,8 @@
55
"dfs": "DFS",
66
"bfs": "BFS",
77
"dijkstra": "Dijkstra",
8-
"bellman_ford": "Bellman-Ford"
8+
"bellman_ford": "Bellman-Ford",
9+
"floyd_warshall": "Floyd-Warshall"
910
}
1011
},
1112
"search": {

‎algorithm/graph_search/floyd_warshall/desc.json

+16
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,16 @@
1+
{
2+
"Floyd-Warshall": "Floyd–Warshall algorithm is an algorithm for finding shortest paths in a weighted graph with positive or negative edge weights (but with no negative cycles)",
3+
"Applications": [
4+
""
5+
],
6+
"Complexity": {
7+
"time": "worst O(|V|<sup>3</sup>)",
8+
"space": "worst O(|V|<sup>2</sup>)"
9+
},
10+
"References": [
11+
"<a href='https://en.wikipedia.org/wiki/Floyd–Warshall_algorithm'>Wikipedia</a>"
12+
],
13+
"files": {
14+
"shortest_paths": "Finding the shortest path between all nodes"
15+
}
16+
}

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

+34
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
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;
17+
}
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++)
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++)
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]);
31+
}
32+
tracer._pace(200);
33+
tracer._print('finding the shortest paths from and to all nodes');
34+
FloydWarshall();

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

+10
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,10 @@
1+
var tracer = new WeightedDirectedGraphTracer();
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 = WeightedDirectedGraph.random(10, .4, 1, 9);
10+
tracer._setData(G);

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

+42-50
Original file line numberDiff line numberDiff line change
@@ -3,74 +3,66 @@ tracer._sleep(1000);
33
tracer._pace(500);
44

55
function mergeSort(start, end) {
6-
if (Math.abs(end - start) <= 1) {
7-
return [];
8-
}
9-
6+
if (Math.abs(end - start) <= 1) return [];
107
var middle = Math.ceil((start + end) / 2);
118

129
mergeSort(start, middle);
1310
mergeSort(middle, end);
14-
15-
tracer._print('divide left[' + start + ', ' + (middle-1) + '], right[' + (middle) + ', ' + (end-1) + ']');
1611

12+
tracer._print('divide left[' + start + ', ' + (middle - 1) + '], right[' + (middle) + ', ' + (end - 1) + ']');
1713
return mergeSort.merge(start, middle, end);
1814
}
1915

20-
mergeSort.merge = function (start, middle, end) {
21-
var left = Array();
22-
var right = Array();
23-
24-
var leftSize = middle - start;
25-
var rightSize = end - middle;
26-
var maxSize = Math.max(leftSize, rightSize);
27-
var size = end - start;
16+
mergeSort.merge = function(start, middle, end) {
17+
const leftSize = middle - start;
18+
const rightSize = end - middle;
19+
const maxSize = Math.max(leftSize, rightSize);
20+
const size = end - start;
21+
var left = [];
22+
var right = [];
2823
var i;
2924

3025
for (i = 0; i < maxSize; i++) {
31-
if (i < leftSize) {
32-
left.push(D[start + i]);
33-
tracer._select(start + i);
34-
tracer._print('insert value into left array[' + i +'] = ' + D[start + i]);
35-
}
36-
if (i < rightSize) {
37-
right.push(D[middle + i]);
38-
tracer._select(middle + i);
39-
tracer._print('insert value into right array[' + i +'] = ' + D[middle + i]);
40-
}
26+
if (i < leftSize) {
27+
left.push(D[start + i]);
28+
tracer._select(start + i);
29+
tracer._print('insert value into left array[' + i + '] = ' + D[start + i]);
30+
}
31+
if (i < rightSize) {
32+
right.push(D[middle + i]);
33+
tracer._select(middle + i);
34+
tracer._print('insert value into right array[' + i + '] = ' + D[middle + i]);
35+
}
4136
}
4237
tracer._print('left array = [' + left.join(', ') + '],' + 'right array = [' + right.join(', ') + ']');
43-
38+
4439
i = 0;
4540
while (i < size) {
46-
if (left[0] && right[0]) {
47-
if (left[0] > right[0]) {
48-
D[start + i] = right.shift();
49-
tracer._print('rewrite from right array[' + i + '] = ' + D[start+i]);
41+
if (left[0] && right[0]) {
42+
if (left[0] > right[0]) {
43+
D[start + i] = right.shift();
44+
tracer._print('rewrite from right array[' + i + '] = ' + D[start + i]);
45+
} else {
46+
D[start + i] = left.shift();
47+
tracer._print('rewrite from left array[' + i + '] = ' + D[start + i]);
48+
}
49+
} else if (left[0]) {
50+
D[start + i] = left.shift();
51+
tracer._print('rewrite from left array[' + i + '] = ' + D[start + i]);
5052
} else {
51-
D[start + i] = left.shift();
52-
tracer._print('rewrite from left array[' + i + '] = ' + D[start+i]);
53+
D[start + i] = right.shift();
54+
tracer._print('rewrite from right array[' + i + '] = ' + D[start + i]);
5355
}
54-
} else if (left[0]) {
55-
D[start + i] = left.shift();
56-
tracer._print('rewrite from left array[' + i + '] = ' + D[start+i]);
57-
} else {
58-
D[start + i] = right.shift();
59-
tracer._print('rewrite from right array[' + i + '] = ' + D[start+i]);
60-
}
61-
62-
tracer._deselect(start + i);
63-
tracer._notify(start + i);
64-
65-
i++;
66-
}
67-
68-
tempArray = Array();
69-
for (i=start; i<end; i++) {
70-
tempArray.push(D[i]);
56+
57+
tracer._deselect(start + i);
58+
tracer._notify(start + i);
59+
i++;
7160
}
61+
62+
tempArray = [];
63+
for (i = start; i < end; i++) tempArray.push(D[i]);
7264
tracer._print('merged array = [' + tempArray.join(', ') + ']');
73-
}
65+
};
7466

75-
mergeSort(0, D.length)
67+
mergeSort(0, D.length);
7668
tracer._print('sorted array = [' + D.join(', ') + ']');

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

+8-3
Original file line numberDiff line numberDiff line change
@@ -1,32 +1,37 @@
11
tracer._print('original array = [' + D.join(', ') + ']');
22
tracer._sleep(1000);
33
tracer._pace(500);
4+
45
function quicksort(low, high) {
56
if (low < high) {
67
var p = partition(low, high);
78
quicksort(low, p - 1);
89
quicksort(p + 1, high);
910
}
1011
}
12+
1113
function partition(low, high) {
1214
var pivot = D[high];
1315
tracer._selectSet([low, high]);
1416
var i = low;
17+
var temp;
18+
1519
for (var j = low; j < high; j++) {
1620
if (D[j] <= pivot) {
17-
var temp = D[i];
21+
temp = D[i];
1822
D[i] = D[j];
1923
D[j] = temp;
2024
tracer._notify(i, j);
2125
i++;
2226
}
2327
}
24-
var temp = D[i];
28+
temp = D[i];
2529
D[i] = D[high];
2630
D[high] = temp;
2731
tracer._notify(i, high);
2832
tracer._deselectSet([low, high]);
2933
return i;
3034
}
35+
3136
quicksort(0, D.length - 1);
32-
tracer._print('sorted array = [' + D.join(', ') + ']');
37+
tracer._print('sorted array = [' + D.join(', ') + ']');

0 commit comments

Comments
 (0)