SCT Lecture 05: Shortest Paths

On January 27, 2012, I gave a lecture on Shortest Path Algorithms. The reason for the long break between lecture 4 and lecture 5 was because we were doing practice activities at SCT. For example, we had an activity where you had to design test cases to break a certain program. Anyway, this lecture was about shortest path algorithms.

One major component of computer science theory is graph theory. Specifically, finding the best or shortest path from one node to another. Some of the most common methods for finding the shortest path are Dijkstra with heap, Dijkstra without heap, Floyd-Warshall, and Bellman-Ford. In terms of contest programming, the trick is figuring out which algorithm to use, when. The lecture can be found on the Senior Computer Team website, or viewed here: