Module: Single source shortest paths

Bellman-Ford algorithm, shortest paths in direct acyclic graphs, Dijsktra’s algorithm.

Learning Outcomes

Apply single source shortest path algorithms, including:

Application of the Bellman-Ford algorithm.
Application to directed acyclic graphs.

Readings

Introduction to single source shortest paths

Properties of the problem, supporting algorithms

Screencast Suthers 19 min

Bellman-Ford and DAGS shortest paths

The Bellman-Ford algorithm

Screencast Suthers 20 min

Dijkstra's algorithm for single source shortest paths

Dijkstra’s algorithm

Screencast Suthers 20 min

CLRS 24 - Single Source Shortest Paths (24.1 - 24.3)

Bellman-Ford algorithm, SSSP in directed acyclic graphs, Dijkstra’s algorithm

Textbook 20 pages

Sedgewick 31 - Weighted graphs

Minimum spanning trees, shortest path, dense paths, geometric problems

Textbook 14 pages

Notes on single source shortest paths

Shortest paths problem, Bellman-Ford algorithm, Shortest paths in a DAG, Dijkstra’s algorithm

Notes

Experiential Learning

Experience single source shortest paths (again)

Playing with Bellman-Ford, Dijkstra’s algorithm, and DAGs

Homework