Shortest Path Problem
From Rice Wiki
Definitions
A path is a sequence of nodes such that for all consecutive nodes, there exist an edge
Let there be a weight assigned to each edge.
Single Source Shortest Path (SSSP)
Given a graph , source node , output the shortest path from the source
Variants
- Single destination problem: shortest path from all nodes to a single destination
- Single pair problem: Shortest path between input pair
Suboptimality
Given is the shortest path.
Prove that is the shortest path between and the end.
For contradiction, assume is not optimal. There must be such that
Adding the path back, it is clear that it doesn't work.