Skip to content

Single Source Shortest Paths

Lecture date: Friday, October 11, 2019

Synopsis

A single source shortest path algorithm discovers the shortest paths between a single node and all the other nodes. There are three algorithms that can do this, depending on the situation.

  • Unweighted graphs use BFS
  • Weighted graphs with no negative edges use Dijkstra’s algoritm
  • Weighted graphs with negative edges use the Bellman Ford algorithm.
  • Competitive Programming 3, section 4.4

Problem

Videos