Single-Source Shortest Path Problem (Graphs: Algorithms & Theory)
2Today we learn about a classic optimization problem on graphs called the single-source shortest path problem! Note that I introduce it here using undirected graphs, there is a flavour of this with directed graphs too. Many of the ideas are similar.
Time Stamps:
0:00 Opening, what is a shortest s-t path? Note that if a path has no edges, its length is 0.
5:00 A subpath of a shortest s-t path is also a shortest path, proof!
19:25 There is a shortest-path tree of s.
20:58 Example of shortest-path tree, remarks about the structure of the tree. What is the single-source shortest path problem?
25:38 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