Level 2 NCEA Networks - Shortest Path (Dijkstra’s Algorithm) — Transcript

Full transcript

1. 0:01kia ora and welcome to a lesson on level
2. 0:03two networks specifically the shortest
3. 0:06path and more specifically using
4. 0:08dijkstra's algorithm to find the
5. 0:10shortest path and
6. 0:12they'll potentially be arguments as to
7. 0:14the pronunciation of that name but it's
8. 0:16the name the way i've always been told
9. 0:18to pronounce your name so that's how i'm
10. 0:20using it today if you have an
11. 0:22alternative method
12. 0:23which is more correct
13. 0:25good on you um
14. 0:27but that's that's how i've been taught
15. 0:29to say it i apologize if it is
16. 0:31incredibly wrong
17. 0:33okay
18. 0:33so
19. 0:34first of all
20. 0:36what is the shortest path well the
21. 0:37shortest path
22. 0:38basically says if you want to go from
23. 0:40one node
24. 0:41to another node
25. 0:43what is the shortest way you can
26. 0:44navigate this network to get from that
27. 0:47node
28. 0:48to the other node okay so if i want to
29. 0:50go from a to g there's lots of different
30. 0:52ways i can go from a to g
31. 0:54as shown in here i can go very basic
32. 0:56just around the outside i can go
33. 0:58crazy all over the place if i really
34. 1:00wanted to but obviously we're trying to
35. 1:03find the shortest version of that so
36. 1:04that's why we're going to use dijkstra's
37. 1:06algorithm
38. 1:08so looking at dijktras algorithm it says
39. 1:11give the starting node a value of zero
40. 1:13and this is an abridged version of
41. 1:15dijkstra's algorithm without an extra
42. 1:17bit of work but it's all we're going to
43. 1:18need for our purposes so we're going to
44. 1:21use this so give a starting node a value
45. 1:24of 0.
46. 1:25it then says to put a box around the
47. 1:27node you are at
48. 1:29and then travel off the edges from node
49. 1:31and label the connect nodes with value
50. 1:33of travel
51. 1:34if there is no
52. 1:35current value or the value that is there
53. 1:38is higher than the new value and that
54. 1:40will sound very confusing for now but
55. 1:42i'll hopefully try and explain that a
56. 1:43bit better whilst we're going through it
57. 1:45step 4 says looking at the network
58. 1:47select the next smallest valued node
59. 1:49that is not boxed if this is the end
60. 1:51node stop and expect inspect which root
61. 1:54creator this value if not repeat from
62. 1:56step two so you keep bouncing back step
63. 1:58two until you're at the end basically
64. 2:00so let's put this into practice because
65. 2:03those written instructions aren't
66. 2:04necessarily going to be the easiest
67. 2:05thing to start so if i wanted to go from
68. 2:07a to
69. 2:09g
70. 2:11how will that look so we're going to go
71. 2:13to our start point right a and we're
72. 2:15going to say at a we are zero because
73. 2:17we've not traveled anywhere
74. 2:19okay the next step says put a box around
75. 2:21the node you're at so i'm going to put a
76. 2:22box around the zero
77. 2:25and then step three says travel off the
78. 2:27edges
79. 2:28um from the node and label connect knows
80. 2:30the value of travel if there's no
81. 2:32current value of a value
82. 2:34there is ha sorry the value
83. 2:37there is a higher than the new value
84. 2:39okay
85. 2:40so from a i can go to b which is six
86. 2:43there is no number there so i'm going to
87. 2:45write the number six
88. 2:46and from a
89. 2:49i can also go to c
90. 2:51and there's no value there so i'm going
91. 2:52to write the number seven those are the
92. 2:54only two places i can go
93. 2:56from a
94. 2:58okay so i've done step three now and
95. 3:00i've labeled them because there's no
96. 3:01value step four says looking up network
97. 3:04select the next smallest valued node
98. 3:06that is not boxed
99. 3:07assuming you're not selecting the end
100. 3:09node which is going to be g so i'm not
101. 3:10going to worry about that clause until
102. 3:12we get to g
103. 3:13so
104. 3:15we've done all the ways from a we're now
105. 3:17looking at a diagram again there's no
106. 3:19information on these nodes okay there's
107. 3:21no value here so we're only considering
108. 3:23these two nodes and their values and
109. 3:26we're going to select the smallest of
110. 3:27those two values which is the six
111. 3:31and we're going to go back to step two
112. 3:32which says put a box around that number
113. 3:34so we'll put a box around b
114. 3:36okay and now we're going to inspect from
115. 3:38b so we're now at b we're going to look
116. 3:40at
117. 3:41all the different places we could go
118. 3:42from b so there's no point going back to
119. 3:44a because we've already put box there
120. 3:46distance was zero however from b we
121. 3:48could go to c
122. 3:50so we say
123. 3:51six plus six
124. 3:53which is twelve total
125. 3:55is twelve smaller number seven
126. 3:58if it's not smaller than seven we're not
127. 4:00going to do anything
128. 4:02uh if it was smaller than seven would
129. 4:04cross out the seven and write our new
130. 4:06number but 12 is not smaller than seven
131. 4:07so we're not going to do that
132. 4:09so from b we can also then travel to d
133. 4:13which is in total eight because six plus
134. 4:16two is eight there's no number there so
135. 4:18i'm gonna write the number eight there
136. 4:21and then from b we can also travel to e
137. 4:24which is six plus five which is eleven
138. 4:26again there's no number there so we're
139. 4:28going to write the number there
140. 4:2911 and now we have gone to every place
141. 4:33we can go to
142. 4:34from b so there's no point looking at
143. 4:37that one this one wasn't smaller than
144. 4:39seven so we didn't do anything this one
145. 4:41had no number this one had no number so
146. 4:43we wrote the total value
147. 4:45so far traveled
148. 4:47okay
149. 4:48now we've done all that we're now going
150. 4:50to look at our diagram again and we're
151. 4:52going to look at the places where we
152. 4:54have numbers eleven eight and seven and
153. 4:56we're going to select the smallest of
154. 4:58those three which is down at c
155. 5:00seven and we're gonna put a box around
156. 5:03it
157. 5:03once we've put our box around it we're
158. 5:05gonna say from c where can we go so
159. 5:07there's no point going to a because
160. 5:08there's already a box there's no point
161. 5:10going to b because there's already a box
162. 5:12however from c we could go to d so what
163. 5:14is seven plus three well seven plus
164. 5:16three is ten is it smaller than eight no
165. 5:19so we're not going to write the ten down
166. 5:21so we're gonna leave that alone
167. 5:22but we can go from c to f
168. 5:257 plus 6 is 13 there's no number there
169. 5:28so we're going to write the number 13.
170. 5:31okay
171. 5:31now we've considered all the paths from
172. 5:33c
173. 5:35we're going to go back to looking at
174. 5:36these numbers and choose our smallest so
175. 5:39the smallest here
176. 5:40is this eight
177. 5:42okay so this number here is our smallest
178. 5:45be eight okay
179. 5:47so we're going to put a box around our
180. 5:49eight
181. 5:51and now we're going to look at all the
182. 5:52places we can go from d so we can go
183. 5:54from d to e which is far more which will
184. 5:57take us 12. it's not smaller than 11 so
185. 6:00we're not going to choose it
186. 6:02from d to f
187. 6:03that's eight plus five which is 13 which
188. 6:06is the same as what's already there so
189. 6:08it doesn't matter which one of those two
190. 6:09we're going to choose okay
191. 6:11but there's two ways of getting to about
192. 6:1313
193. 6:14and that's the only other place because
194. 6:16the other paths are back to boxes
195. 6:19okay so now we've considered all the
196. 6:20places we can go from d we're going to
197. 6:22go back to looking at the nodes where
198. 6:24there's a value 11 and 13 choosing the
199. 6:26smaller of a 2
200. 6:28which is v11
201. 6:30and saying from here where can we go
202. 6:32well we can either go down to f which is
203. 6:3411 plus 3
204. 6:36which is 14
205. 6:38that's bigger so we're not going to
206. 6:39change this at all
207. 6:41and and we e to g
208. 6:43is 7 more so that is 18
209. 6:46okay that's
210. 6:47gonna stay there because it had no value
211. 6:50and now we've done all the places we can
212. 6:51go from e
213. 6:55and by the way this will probably if
214. 6:57you've just been watching this non-stop
215. 6:58you're probably sitting here going i
216. 7:00kind of lost it about two minutes ago
217. 7:02because he just kept talking
218. 7:04pause the video go back maybe check
219. 7:07the steps but it's just following the
220. 7:09same algorithm i'm just constantly going
221. 7:11to here to here going back to two
222. 7:14from two to three too far to back to two
223. 7:16okay
224. 7:18now i'm at this point here where again
225. 7:19i'm selecting up these two the smallest
226. 7:22numbers still 13
227. 7:24so i'm going to select my 13
228. 7:27okay
229. 7:28and i'm going to say from f there's only
230. 7:29one place i can go because i everywhere
231. 7:31else is already boxed which is to g
232. 7:34is 13 plus 8 smaller than 18 no because
233. 7:37it's 21 so 21 is bigger
234. 7:39so that's our end
235. 7:42and now
236. 7:43at our final node which is 18 which is
237. 7:46actually where we're ending up
238. 7:48that is the value which will take us to
239. 7:52there okay so this is going to be 18 so
240. 7:54we're going to put a box around it
241. 7:57unfortunately in this one i didn't get
242. 7:59an opportunity to show you crossing out
243. 8:01a value i'm replacing it with a new
244. 8:03value but if
245. 8:05when i inspected one of these edges if
246. 8:07it had been smaller the total value then
247. 8:10i would have crossed out the value that
248. 8:12was already there and written my new
249. 8:13value to replace it okay
250. 8:16so
251. 8:18so the final step said looking at the
252. 8:20network select smallest value node of
253. 8:21the box if this nodes um if this is the
254. 8:24endnote stop and inspect which route
255. 8:26created this value so now we're going to
256. 8:27do the inspect which route created this
257. 8:29value
258. 8:30so from g i'm going to work backwards
259. 8:33okay so i'm going to say
260. 8:35which of these edges makes sense so g is
261. 8:3818. if i was to go eight back
262. 8:41that would take me to ten
263. 8:43however this value here is not ten
264. 8:46so
265. 8:48let's have a look at the other place i
266. 8:49can go and grow from g is seven back
267. 8:51this way eighteen seven back is 11. so
268. 8:54this is
269. 8:56part of my path okay because it makes
270. 8:58sense 18
271. 9:00minus 7 gave me 11. so this is true
272. 9:05from a
273. 9:06if i was to look going along these edges
274. 9:09which one of these three situations
275. 9:11actually makes sense well eleven minus
276. 9:13three is not thirteen
277. 9:15eleven minus four is not seven but
278. 9:18eleven minus five is six
279. 9:20so this path here
280. 9:23this five path is part of my shortest
281. 9:26path
282. 9:27and then from b i go is six minus two
283. 9:30eight no six minus two is four
284. 9:33is six minus six seven no it is zero and
285. 9:36is six minus six zero yes it is so this
286. 9:39must also be part of my path
287. 9:42so my shortest path from a to g
288. 9:44would go
289. 9:46a
290. 9:47to b
291. 9:48to e
292. 9:49to g
293. 9:51and is equal to
294. 9:5318
295. 9:54kilometers minutes dollars depending on
296. 9:58whatever units you are using to describe
297. 10:00your network
298. 10:02and i
299. 10:05thought i couldn't add for a second
300. 10:07but no i i i can add 6 out of 5 out of 7
301. 10:10is 18. so that is true um so that is
302. 10:13dytra's algorithm to find the shortest
303. 10:16path okay you can find the shots path
304. 10:19via inspection however the maximum you
305. 10:21can get for shots pathfire inspection is
306. 10:23achieved so if i just looked at this
307. 10:25network and going oh yeah i can see
308. 10:26abegs it's going to be the shyness at
309. 10:2818.
310. 10:29i can save that and you'll get achieved
311. 10:32and there are other methods of a van
312. 10:34dijkstra's algorithm there's a tree
313. 10:35diagram method
314. 10:36uh however from merit and excellence
315. 10:39there's actually a bit more explanation
316. 10:40that needs to go into it than dijkstra's
317. 10:42and i find dijkstra's overall the
318. 10:45easiest
319. 10:46of the methods to use for those higher
320. 10:49awarded grades as well as just from
321. 10:52making sure you don't make a mistake
322. 10:54okay because the tree diagram method can
323. 10:56be a bit fiddly and easy to make
324. 10:58mistakes on however it does kind of make
325. 11:00a bit more sense
326. 11:01dijkstra's is very kind of abstracty
327. 11:04however it does get you to the answer a
328. 11:07bit easier okay
329. 11:09so
330. 11:11this is nitrous algorithm shots path and
331. 11:13you can use it for any network to find
332. 11:14the shortest path
333. 11:16hopefully this kind of makes sense if
334. 11:18not maybe re-watch it go a bit slower
335. 11:21and
336. 11:22there if you're wanting more videos on
337. 11:24network there's a video on
338. 11:25traversability as well as a video on the
339. 11:28minimum spanning tree for you to use
340. 11:30hopefully this is helpful
341. 11:32uh good luck and bye