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

Lines changed: 2 additions & 0 deletions
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

Lines changed: 7 additions & 3 deletions
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

Lines changed: 2 additions & 2 deletions
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

Lines changed: 5 additions & 6 deletions
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

Lines changed: 6 additions & 7 deletions
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

Lines changed: 16 additions & 0 deletions
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

Lines changed: 49 additions & 0 deletions
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

Lines changed: 10 additions & 0 deletions
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

Lines changed: 16 additions & 0 deletions
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

Lines changed: 34 additions & 0 deletions
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();

0 commit comments

Comments
 (0)