Shortest Path problem
Knapsack problem
Tower of Hanoi Puzzle
Travelling Salesman Problem (??)
Critical Path Problem (Chapter 10)
Dijkstra’s Algorithm (BYO) (details in due course)
9.1 Shortest Path Problem
9.1.1 Terminology
Path
Predecessor
Successor
Immediate Predecessor
immediate Successor
Origin (no predecessor)
Destination (no successors)
Cycle
Acyclic graph
Problem Statement
Given a directed graph where each arc is assigned a numerical length, we want to find the shortest path between a specified origin s and a specified destination t, where the length of a path is equal to the sum of the arc lengths on that path.