Skip to content

Commit 6624e8b

Browse files
author
Raghav Dua
committed
Merge pull request algorithm-visualizer#1 from parkjs814/gh-pages
update
2 parents f05d2e2 + 22fcb4a commit 6624e8b

File tree

27 files changed

+1159
-921
lines changed

27 files changed

+1159
-921
lines changed

‎README.md

+2
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,6 @@
11
# Algorithm Visualizer
2+
3+
[![Join the chat at https://gitter.im/parkjs814/AlgorithmVisualizer](https://badges.gitter.im/parkjs814/AlgorithmVisualizer.svg)](https://gitter.im/parkjs814/AlgorithmVisualizer?utm_source=badge&utm_medium=badge&utm_campaign=pr-badge&utm_content=badge)
24
http://parkjs814.github.io/AlgorithmVisualizer
35

46
![Algorithm Visualizer](http://i.giphy.com/3o6EhJFgsyShX6MHeM.gif)

‎algorithm/category.json

+7-3
Original file line numberDiff line numberDiff line change
@@ -4,7 +4,9 @@
44
"list": {
55
"dfs": "DFS",
66
"bfs": "BFS",
7-
"bellman_ford": "BELLMAN_FORD"
7+
"dijkstra": "Dijkstra",
8+
"bellman_ford": "Bellman-Ford",
9+
"floyd_warshall": "Floyd-Warshall"
810
}
911
},
1012
"search": {
@@ -19,7 +21,9 @@
1921
"insertion": "Insertion Sort",
2022
"selection": "Selection Sort",
2123
"bubble": "Bubble Sort",
22-
"quick": "Quicksort"
24+
"quick": "Quicksort",
25+
"merge": "Mergesort",
26+
"heap" : "Heap Sort"
2327
}
2428
},
2529
"etc": {
@@ -29,4 +33,4 @@
2933
"scratch_paper": "<i class='fa fa-code'></i> Scratch Paper"
3034
}
3135
}
32-
}
36+
}

‎algorithm/graph_search/bellman_ford/desc.json

+2-2
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,5 @@
11
{
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.",
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 Dijkstra's Shortest Path Algorithm because it allows NEGATIVE weights unlike Dijkstra's.",
33
"Applications": [
44
"Packet Routing - A variation of BF is used in the Distance vector Routing Protocol"
55
],
@@ -13,4 +13,4 @@
1313
"files": {
1414
"shortest_path": "Finding the shortest path"
1515
}
16-
}
16+
}

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

+5-6
Original file line numberDiff line numberDiff line change
@@ -3,10 +3,10 @@ function BELLMAN_FORD (src, dest) {
33

44
for (var i = 0; i < G.length; i++) {
55
weights [i] = MAX_VALUE;
6-
tracer._weight (i, MAX_VALUE);
6+
tracer._weight(i, weights[i]);
77
}
88
weights [src] = 0;
9-
tracer._weight (src, 0);
9+
tracer._weight(src, 0);
1010

1111
tracer._print ('Initializing weights to: [' + weights + ']');
1212
tracer._print ('');
@@ -21,14 +21,13 @@ function BELLMAN_FORD (src, dest) {
2121
for (var currentNodeNeighbor = 0; currentNodeNeighbor <= G.length; currentNodeNeighbor++) {
2222
if (G [currentNode] [currentNodeNeighbor]) { //proceed to relax Edges only if a particular weight != 0 (0 represents no edge)
2323
tracer._print ('Exploring edge from ' + currentNode + ' to ' + currentNodeNeighbor + ', weight = ' + G [currentNode] [currentNodeNeighbor]);
24-
tracer._visit (currentNodeNeighbor, currentNode, undefined);
2524

2625
if ( weights [currentNodeNeighbor] > (weights [currentNode] + G [currentNode] [currentNodeNeighbor]) ) {
2726
weights [currentNodeNeighbor] = weights [currentNode] + G [currentNode] [currentNodeNeighbor];
2827
tracer._print ('weights [' + currentNodeNeighbor + '] = weights [' + currentNode + '] + ' + G [currentNode] [currentNodeNeighbor]);
2928
}
30-
31-
tracer._leave (currentNodeNeighbor, currentNode, undefined);
29+
tracer._visit (currentNodeNeighbor, currentNode, weights [currentNodeNeighbor]);
30+
tracer._leave (currentNodeNeighbor, currentNode);
3231
}
3332
}
3433
}
@@ -55,7 +54,7 @@ function BELLMAN_FORD (src, dest) {
5554
return weights [dest];
5655
}
5756

58-
var src = Math.random() * G.length | 0, dest;
57+
var src = Math.random() * G.length | 0, dest;
5958
var MAX_VALUE = Infinity;
6059
var minWeight;
6160

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

+6-7
Original file line numberDiff line numberDiff line change
@@ -1,10 +1,9 @@
1-
var tracer = new DirectedGraphTracer();
1+
var tracer = new WeightedDirectedGraphTracer();
22
var G = [
3-
[0,-1,4,0,0],
4-
[0,0,3,2,2],
5-
[0,0,0,0,0],
6-
[0, 1,5,0,0],
7-
[0,0,0,-3,0]
3+
[0, -1, 4, 0, 0],
4+
[0, 0, 3, 2, 2],
5+
[0, 0, 0, 0, 0],
6+
[0, 1, 5, 0, 0],
7+
[0, 0, 0, -3, 0]
88
];
9-
109
tracer._setData(G);

‎algorithm/graph_search/dijkstra/desc.json

+16
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,16 @@
1+
{
2+
"Dijkstra": "Dijkstra's algorithm is an algorithm for finding the shortest paths between nodes in a graph, which may represent, for example, road networks. It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three years later.",
3+
"Applications": [
4+
"Ar."
5+
],
6+
"Complexity": {
7+
"time": "worst O(|V|<sup>2</sup>)",
8+
"space": "worst O(|V|)"
9+
},
10+
"References": [
11+
"<a href='https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm'>Wikipedia</a>"
12+
],
13+
"files": {
14+
"shortest_path": "Finding the shortest path between two nodes"
15+
}
16+
}

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

+49
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,49 @@
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]);
40+
}
41+
42+
var s = Math.random() * G.length | 0; // s = start node
43+
var e; // e = end node
44+
do {
45+
e = Math.random() * G.length | 0;
46+
} while (s == e);
47+
tracer._pace(100);
48+
tracer._print('finding the shortest path from ' + s + ' to ' + e);
49+
Dijkstra(s, e);

‎algorithm/graph_search/dijkstra/shortest_path/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/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/search/binary_search/iterative/code.js

+2-2
Original file line numberDiff line numberDiff line change
@@ -9,9 +9,9 @@ function BinarySearch(array, element) { // array = sorted array, element = eleme
99
testElement = array[middleIndex];
1010

1111
tracer._print('Searching at index: ' + middleIndex);
12-
tracer._selectSet([minIndex, maxIndex]);
12+
tracer._select(minIndex, maxIndex);
1313
tracer._notify(middleIndex);
14-
tracer._deselectSet([minIndex, maxIndex]);
14+
tracer._deselect(minIndex, maxIndex);
1515

1616
if (testElement < element) {
1717

‎algorithm/search/binary_search/recursive/code.js

+2-2
Original file line numberDiff line numberDiff line change
@@ -8,9 +8,9 @@ function BinarySearch(array, element, minIndex, maxIndex) { // array = sorted ar
88
var testElement = array[middleIndex];
99

1010
tracer._print('Searching at index: ' + middleIndex);
11-
tracer._selectSet([minIndex, maxIndex]);
11+
tracer._select(minIndex, maxIndex);
1212
tracer._notify(middleIndex);
13-
tracer._deselectSet([minIndex, maxIndex]);
13+
tracer._deselect(minIndex, maxIndex);
1414

1515
if (testElement < element) {
1616
tracer._print('Going right.');

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

+58
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,58 @@
1+
tracer._print('Original array = [' + D.join(', ') + ']');
2+
3+
function heapSort(array, size) {
4+
var i, j, temp;
5+
6+
for (i = Math.ceil(size / 2) - 1; i >= 0; i--) {
7+
heapify(array, size, i);
8+
}
9+
10+
for (j = size - 1; j >= 0; j--) {
11+
temp = array[0];
12+
array[0] = array[j];
13+
array[j] = temp;
14+
15+
tracer._notify(0, j);
16+
tracer._select(j);
17+
18+
heapify(array, j, 0);
19+
tracer._print('Swapping elements : ' + array[0] + ' & ' + array[j]);
20+
21+
tracer._deselect(j);
22+
}
23+
}
24+
25+
function heapify(array, size, root) {
26+
27+
var largest = root;
28+
var left = 2 * root + 1;
29+
var right = 2 * root + 2;
30+
var temp;
31+
32+
if (left < size && array[left] > array[largest]) {
33+
largest = left;
34+
}
35+
36+
if (right < size && array[right] > array[largest]) {
37+
largest = right;
38+
}
39+
40+
if (largest != root) {
41+
temp = array[root];
42+
array[root] = array[largest];
43+
array[largest] = temp;
44+
45+
tracer._notify(largest, root);
46+
47+
tracer._print('Swapping elements : ' + array[root] + ' & ' + array[largest]);
48+
49+
heapify(array, size, largest);
50+
}
51+
}
52+
53+
tracer._sleep(1000);
54+
tracer._pace(800);
55+
56+
heapSort(D, 10);
57+
58+
tracer._print('Final array = [' + D.join(', ') + ']');

‎algorithm/sorting/heap/basic/data.js

+3
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,3 @@
1+
var tracer = new Array1DTracer();
2+
var D = Array1D.random(10);
3+
tracer._setData(D);

‎algorithm/sorting/heap/desc.json

+13
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,13 @@
1+
{
2+
"Heap Sort": "Heapsort is a comparison-based sorting algorithm. Heapsort can be thought of as an improved selection sort: like that algorithm, it divides its input into a sorted and an unsorted region, and it iteratively shrinks the unsorted region by extracting the largest element and moving that to the sorted region. The improvement consists of the use of a heap data structure rather than a linear-time search to find the maximum.",
3+
"Complexity": {
4+
"time": "worst O(n log n), best O(n log n), average O(n log n)",
5+
"space": "worst O(1) auxiliary"
6+
},
7+
"References": [
8+
"<a href='https://en.wikipedia.org/wiki/Heapsort'>Wikipedia</a>"
9+
],
10+
"files": {
11+
"basic": "Basic"
12+
}
13+
}

0 commit comments

Comments
 (0)