Correctness of Dijkstra's Algorithm (Graphs: Algorithms & Theory)

Channel:

PageWizard Games, Learning & Entertainment

Subscribers:

780

Published on November 4, 2022 3:15:20 PM ● Video Link: https://www.youtube.com/watch?v=TIozeaeHZEQ

Duration: 30:50

44 views

3

In today's lesson, we learn how we could prove the correctness of Dijkstra's algorithm. Dijkstra's algorithm produces a solution to the single-source shortest path problem, a shortest path tree of source vertex s. Here we use contradiction.

Time Stamps:
0:00 Opening gameplan
0:49 Dijkstra's algorithm produces a spanning tree
3:00 Key observation
6:46 Theorem for the invariant
29:10 Corollary for correctness
30:30 Closing
Have a beautiful day!

Supporters (to date of publication, by tier (top to bottom)):
----------------------------------------------------------
Patreon Supporters (General Support):
Draikou
Patreon Supporters (Basic Support):
Patreon Supporters (Supporter Access!):
Eric R
-----------------------------------------------------------
Become a supporter today! To support my work and mission to provide free or accessible Computer Science education (especially in theory), subscribe to the channel, share my videos. Please donate and contribute to support my work for more content:
PATREON: https://www.patreon.com/PageWizard
SUBSCRIBESTAR: https://www.subscribestar.com/drpage
PAYPAL: https://paypal.me/pagewizard

Follow also at:
FACEBOOK: https://www.facebook.com/DanielRPage
TWITTER: https://twitter.com/PageWizardGLE
QUORA: https://www.quora.com/profile/Daniel-R-Page
TWITCH: https://www.twitch.tv/pagewizard

#ComputerScience
#Algorithms
#graphtheory