Algorithm Tutorial: Graphs Part 3: Dijkstra's Algorithm, Weighted Shortest Paths

Prerequisites: You should have a good understanding of the material from Graphs Part 1 and 2. In those sessions, we covered an introduction to what graphs are and how they are used to model problems, the distinction between weighted/unweighted and directed/undirected graphs, common graph representations (adjacency matrix, adjacency list), the definition of the shortest path problem with some example applications, and the BFS algorithm for finding unweighted shortest paths. We also saw a variety of problems that helped us build intuition about how to map problems to BFS. The new material builds on essentially everything above, so it is critical to have a good understanding of it before attending the session.

It follows naturally you should also have a good understanding of the previous material's prereqs: how to program, use basic big-O analysis, and use basic data types such as maps, sets, and lists.

Difficulty: 6.5/10

I will introduce Dijkstra's algorithm, a generalization of BFS that solves the *weighted* shortest path problem, and show a few nice problems that use it. I may also briefly mention some other path finding algorithms such as Bellman-Ford.