CSC270 October 7 Lecture II: Graphs and Makefiles

See the hand-written lecture notes in the Engineering Library



All-pairs shortest paths

- find all connected pairs of nodes
- motivating example: connectivity in a network
- variant: Floyd's shortest path algorithm
- motivating example: "upper bound on transmission time"



Single-source shortest path

- Dijkstra's alg: all shortest paths from a source node
- motivating example: "Erdos number"