In this lesson, we look at another algorithm for solving the single-source shortest-paths problem called Dijkstra’s algorithm. Dijkstra’s algorithm is the preferred algorithm for finding the shortest paths from a single source because it also works for digraphs that have cycles. However, it does fail to work for digraphs with negative edge weights. The principal idea behind Dijkstra’s algorithm appears, in its rudimentary form, in a 1959 paper"A note on two problems in connexion with graphs", Numerische Mathematik 1, 269 – 271 by the famous Dutch computer scientist Edsger Dijkstra.

Get hands-on with 1200+ tech skills courses.