-
Notifications
You must be signed in to change notification settings - Fork 0
/
index.html
56 lines (46 loc) · 2.71 KB
/
index.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<meta http-equiv="X-UA-Compatible" content="ie=edge">
<script>
var clicky_site_ids = clicky_site_ids || [];
clicky_site_ids.push(101222564);
</script>
<script async src="//static.getclicky.com/js"></script>
<title>Dijkstra's Visualizer</title>
<style>
#canvas{
border: 1px solid black;
}
</style>
</head>
<body>
<h1>Dijkstra's Visualizer</h1>
<canvas id="canvas" width=800 height=600>
</canvas>
<div></div>
<button id="populate"> Repopulate graph nodes</button>
<button id="search"> Search for shortest path</button>
<div id="distance" style='display: inline;'> </div>
<div class="slidecontainer" style="display: flex; text-align: center;">
<div style="margin: 10px"><input type="range" min="2" max="30" value="15" class="slider" id="nodeSlider">
<div>Number of Nodes</div>
</div>
<div style="margin: 10px">
<input type="range" min="1" max="50" value="15" class="slider" id="pathFrequency">
<div>Number of Edges</div>
</div>
</div>
<p style="width: 800px">
"Dijkstra's algorithm (or Dijkstra's Shortest Path First algorithm, SPF 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." <a href="https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm">-Wikipedia</a>
<br /><br />This is an interractive visual implementation which can generate a random undirected graph and use Dijkstra's algorithm to draw the shortest path between two randomly selected points, if such a path exists. New graphs can be generated with sliders to adjust the number of nodes and frequency of edges. This implementation follows the original Dijkstra algorithm and stop the search as soon as the target path is found, rather than continuing to build a shortest-path-tree to every node (a common variant on the algorithm).
<br /><br />Known issues: occasionally points or paths will overlap visually without actually sharing a direct graph connection / edge, especially as the graph grows visually cluttered with large numbers of points or edges. The algorithm uses a naive version of a priority queue but worst case runtimes could be improved with a Fibonacci heap based queue.
</p>
<p style='font-size: 12px;'>
Made by <a href='https://www.natedonato.com/'>Nate Donato</a>.
</p>
<script src='./script.js'></script>
</body>
</html>