Single source shortest paths

From Algowiki
Jump to: navigation, search

Input

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

Output

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

Objective

N/A

Complexity

Polynomial

Known algorithms

Dijkstra

Known variants