Single source single target 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. Two nodes [math] s,t \in V [/math]

Output

The length of a shortest [math](s,t)[/math]-path in [math]G[/math] subject to [math]l[/math]

Objective

N/A

Complexity

Polynomial

Known algorithms

Known variants