Why Dijkstra's Algorithm Fails for Negative Weight Edges (Graphs: Algorithms & Theory)
6We learn today why Dijkstra's algorithm does not work when negative weights persist (we consider undirected graphs). The existence of a single negative weight is enough, as seen in the set of counterexamples today!
Remark: When considering shortest simple paths, they do exist, just they may not take the form of a tree as we had before. Computing shortest simple paths when negative weights exist is a much harder problem. Furthermore, in the context of directed graphs, the single edge we add is literally a negative-weight cycle, one has to be careful when considering directed graphs in special cases for Dijkstra for negative weights (though it won't work always, as presented, here).
Time Stamps:
0:00 Opening
0:29 Simple setup (before we get the set of counterexamples, consider when paths are simple first)
2:35 Counterexamples (simple and non-simple path)
7:00 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