Single source single target shortest paths: Difference between revisions
Jump to navigation
Jump to search
(Created page with " == Input == # A directed graph <math>G=(V,A)</math> # an arc weight <math> l(a) \in \mathbb{R}</math> for each arc <math>a \in A</math> # Two nodes <math> s,t \in V </math>...") |
(No difference)
|
Latest revision as of 10:39, 20 October 2014
Input
- A directed graph [math]\displaystyle{ G=(V,A) }[/math]
- an arc weight [math]\displaystyle{ l(a) \in \mathbb{R} }[/math] for each arc [math]\displaystyle{ a \in A }[/math]
- Two nodes [math]\displaystyle{ s,t \in V }[/math]
Output
The length of a shortest [math]\displaystyle{ (s,t) }[/math]-path in [math]\displaystyle{ G }[/math] subject to [math]\displaystyle{ l }[/math]
Objective
N/A
Complexity
Polynomial
Known algorithms
- The A* variant on Dijkstra.