-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy pathdijkstra-visual.html
256 lines (253 loc) · 13.8 KB
/
dijkstra-visual.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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8" />
<meta http-equiv="X-UA-Compatible" content="IE=edge" />
<meta name="viewport" content="width=device-width, initial-scale=1.0" />
<meta name="description" content="breadth first search path finding algorithm">
<meta name="keywords"
content="Dijkstra's shortest path algorithm, shortest path algorithm, dijkastras path finding, graph algorithms, algorithms, visualization, visual, graphs, graph traversal, traversal">
<meta name="author" content="lumunge">
<meta name="HandheldFriendly" content="True" />
<meta property="og:site_name" content="OpenGenus IQ: Computing Expertise & Legacy" />
<meta property="og:type" content="article" />
<meta property="og:title" content="Dijkstras Shortest Path Algorithm Visualization" />
<meta property="og:description"
content="data structures and algorithms visualization, dijkstra's path shortest path algorithm visualization, path finding algorithms, graph algorithms visualization, visual, graphs, graph traversal, traversal" />
<meta property="og:url" content="https://iq.opengenus.org/algorithm-visualization/" />
<meta property="article:published_time" content="2021-12-08T10:39:05.000Z" />
<meta property="article:modified_time" content="2021-12-08T19:39:45.000Z" />
<meta property="article:tag" content="Algorithms" />
<meta property="article:tag" content="Data Structures" />
<meta property="article:tag" content="Visualization" />
<meta property="article:publisher" content="https://www.facebook.com/opengenus" />
<meta name="twitter:card" content="summary" />
<meta name="twitter:title" content="Visualization" />
<meta name="twitter:description"
content="A visualization of dijkastra's shortest path algorithm, graph algorithms, path finding" />
<meta name="twitter:url" content="https://iq.opengenus.org/algorithm-visualization/" />
<meta name="twitter:label1" content="Written by" />
<meta name="twitter:data1" content="Erick Lumunge" />
<meta name="twitter:label2" content="Filed under" />
<meta name="twitter:data2" content="Visualization, Algorithms, Data Structures" />
<meta name="twitter:site" content="@OpenGenus" />
<link
rel="shortcut icon"
type="image/png"
href="./src/assets/images/fav1.ico"
/>
<link rel="stylesheet" href="./src/assets/css/index.min.css">
<link rel="stylesheet" href="./src/assets/css/pathFinding.min.css">
<title>Dijkstra's shortest path algorithm.</title>
</head>
<body>
<div class="menu">
<div class="nav">
<div class="logo">
<a href="index.html">OpenGenus Visuals</a>
</div>
<div class="nav-links">
<a href="bfs-visual.html">bfs</a>
<a href="dfs-visual.html">dfs</a>
<a href="dijkstra-visual.html">dijkstra's</a>
<a href="bellman-ford-visual.html">bellman-ford's</a>
<a href="islands-visual.html">num islands</a>
<a href="max-Island-visual.html">max island</a>
<a href="https://github.com/lumunge/Graph-Algorithms-Visualization/wiki">docs</a>
</div>
</div>
<div class="hamburger">
<span class="bar"></span>
<span class="bar"></span>
<span class="bar"></span>
</div>
</div>
<header>
<div class="heading">
<h2 class="algorithm dijkstras">Dijkstra's shortest path algorithm visualization</h2>
</div>
<div class="controlsContainer">
<div class="visualControls">
<div class="visualSpeed">
<p>Speed</p>
<input type="range" min="1" max="20" value="10" class="speedSlider" />
</div>
<div class="obstacles">
<p>Obstacles</p>
<div class="obstaclesElements">
<input type="range" min="1" value="50" class="obstacleSlider" />
<button class="setWalls btn">walls</button>
</div>
</div>
<div class="controlBtns">
<select name="" class="islandsAlgo" style="display: none;">
<option value="bfs">BFS</option>
<option value="dfs">DFS</option>
</select>
<button class="start btn">start</button>
<button class="findNext btn" style="display: none;">find next</button>
<button class="manual btn">manual</button>
<button class="clearPath btn">clear path</button>
<button class="reset btn">reload</button>
</div>
<div class="tutorialContainer">
<span><img class="info" src="./src/assets/images/icons8-info-60.png" alt=""></span>
<div class="tutorialContent">
<h4>Controls</h4>
<p><span>Speed</span> - increase or decrease the speed of the visualization</p>
<p><span>Obstacles-</span> - create walls/obstacles, on a map these can be buildings or
structures which hinder a path. You can adjust the number of obstacles generated per click.
<br /> - You can also click on the grid cells to create
obstacles.
</p>
<p><span>Start</span> - After adjusting the speed and creating obstacles, you can now start the
visualization to see the workings of the algorithm.</p>
<p><span>Manual</span> - After running the visualization normally you can run it manually to see
how the shortest path was obtained. After the click you can proceed with pressing enter key.
</p>
<p><span>Clear Path</span> - After visualizing, you may opt to clear the path and add more
obstacles.</p>
<p><span>Speed</span> - If the grid becomes to cluttered you can reload it and repeat the above
steps.</p>
</div>
</div>
</div>
<!-- not displayed -->
<div class="hide">
<select class="algo">
<option value=""></option>
</select>
<select class="weight">
<option value=""></option>
</select>
</div>
</div>
</header>
<main>
<div class="visualizationContainer">
<div id="gridContainer"></div>
<div class="notification"></div>
<div class="tutorials">
<div class="tutorial">
<div class="emptyPath"><span class="txt">4</span></div>
<div>This is a node with an assigned weight, which means that from source to a point it will take
4(km/m/cm/hops...)
to get to that point.</div>
</div>
<div class="tutorial">
<div class="stedimg"><span class="txt">A</span></div>
<div>Start Node -> this is the starting point(source),
search for a path starts here.</div>
</div>
<div class="tutorial">
<div class="stedimg"><span class="txt">B</span></div>
<div>End Node -> where the search stops when a path to destination has been found</div>
</div>
<div class="tutorial">
<div class="obstacle"></div>
<div>These act as obstacles, walls. On a real map these may be buildings or structures that may
block
a shorter path to a destination.</div>
</div>
<div class="tutorial">
<div class="selectedPath"><span class="txt">7</span></div>
<div>After the algorithm is complete, we have arrived at the destination, now the shortest path is
highlighted in green with the cost of path written in black inside the path.</div>
</div>
</div>
<div class="algoInfo">
<div>
<div class="infoHeading">
<h3 class="title">Dijkstra's shortest path algorithm</h3>
</div>
<div class="description">
This algorithm finds a shortest path tree from a single source node by building a set of nodes
that
have a minimum distance from the source node. <br />
This algorithm uses a greedy approach in that we find the next best solution in hope that it
will
lead to a generalized optimal solution.
<u>Vertices</u> are denoted by <em>u</em> and <em>v</em>. In our case in the above grid we place
the
weights inside the vertex denoting the weight to get to it. <br>
<u>Weighted edges</u> that connect two nodes (u, v) are denoted as w(u, v). <br>
<u><em>dist</em></u> is an array of distances from source <em>s</em> to every node in the graph.
<em>s</em> is initialized as 0 and for all other nodes we initialize them as ∞.
<em>dist(v) =
∞</em> <br>
We use a <u><b><em>queue (Q)</em></b></u> data structure to store all nodes in the graph and at
the
end of
the
algorithm the queue will be empty. <br>
<u>S</u> - an empty set to indicate which nodes the algorithm has visited. At the end of the
algorithm, S
will contain all nodes of the graph.
</div>
<div class="algo-steps">
<p class="subtitle">Algorithm</p>
<p>
1. While Q is not empty, we pop the node v that is not in <em>S</em> from <em>Q</em> with
the smallest distance <em>dist(v)</em>.
In the first iteration the source node is chosen because we initialized it with 0.
In the following iterations nodes with the smallest weight values will be chosen.
</p>
<p>
2. We add node <em>v</em> to <em>S</em>, to indicate that <em>v</em> has been visited.
</p>
<p>
3. We update <em>dist</em> values of adjacent nodes of the current node <em>v</em> by doing
the following: for each new adjacent node <em>u</em>,
</p>
<p class="nest1">
1. if <em>dist(v) + weight(u,v) < dist(u)</em>, that means there is a minimal distance found
for <em>u</em>.
<p class="nest2">1. update <em>dist(u)</em> to the new minimal distance value.</p>
<p class="nest2">2. Otherwise don't update <em>dist(u).</em></p>
</p>
<p>
4. In the end the algorithm has visited all nodes in the graph and <em>dist</em> array will
contain the shortest path(smallest distance) from source s to destination.
</p>
</div>
<div class="complexity">
<p class="subtitle">Computational complexity</p>
This algorithm takes <b><em>O(V + E log V)</em></b> in the all cases where V is the number of
vertices and E is the number of edges. <br>
It has a <b><em>O(V)</em></b> space complexity. It stores V, the number of vertices.
</div>
<div class="applications">
<p class="subtitle">Applications</p>
<ul>
<li>Open Shortest Path First (OSPF) algorithm for packet routing.</li>
<li>telephone networking.</li>
<li>social network algorithms.</li>
<li>maps and gps navigation software.</li>
<li>Drone/robotic path routing.</li>
<li>Designating a file server.</li>
</ul>
</div>
<div class="reference">
<a href="https://iq.opengenus.org/tag/dijkstra-algorithm/">reference</a>
</div>
</div>
</div>
</div>
</main>
<footer>
<div class="copy">
<p>OpenGenus IQ ©
<script>document.write(/\d{4}/.exec(Date())[0])</script> All rights reserved ™ [email: <a
href="mailto:[email protected]">[email protected]]</a>
</p>
</div>
<div class="links">
<span><a href="https://iq.opengenus.org/"> Top Posts </a></span>
<span><a href="https://www.linkedin.com/company/opengenus"> LinkedIn</a></span>
<span><a href="https://twitter.com/OpenGenus"> Twitter</a></span>
</div>
</footer>
<script src="./dist/main.js"></script>
</body>
</html>