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$, outupt 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

Implementation

All shortest path must have $\leq n-1$ edges. If this condition is not satisfied, there is a cycle in in the path, and therefore it is not the shortest.

 
OPT(a, n-1) = min(w(u,a) + OPT(n-1, u))

where $(u,a)\in E$