Single source shortest paths

Input

1. A directed graph [math]\displaystyle{ G=(V,A) }[/math]
2. an arc weight [math]\displaystyle{ l(a) \in \mathbb{R} }[/math] for each arc [math]\displaystyle{ a \in A }[/math]
3. a root node [math]\displaystyle{ s \in V }[/math]

Output

For each [math]\displaystyle{ v \in V }[/math], a real value [math]\displaystyle{ \delta (v) }[/math], the length of a shortest [math]\displaystyle{ (s,v) }[/math]-path in [math]\displaystyle{ G }[/math] subject to [math]\displaystyle{ l }[/math]

Objective

N/A

Complexity

Polynomial

Known algorithms

Dijkstra