Shortest Path Problem

Definitions

A path is a sequence of nodes $x_{1},x_{2},x_{3},\ldots ,x_{i}$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 $G(V,E),w(e)$, source node $S$, 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 $OPT=x_{1},x_{2},\ldots$ is the shortest path.

Prove that $A=OPT-x_{1}$ is the shortest path between $x_{2}$ and the end.

For contradiction, assume $A$ is not optimal. There must be $B$ such that

$w(B)<w(A)$

Adding the path back, it is clear that it doesn't work.