Shortest Pathcost(path) = sum of edge weights along path Shortest path between vertices s and t
Finding shortest path between two given nodes known as source-target SP problem Variations: single-source SP, all-pairs SP Applications: navigation, routing in data networks, … |