Single source shortest paths: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| Line 4: | Line 4: | ||
# an arc weight <math> l(a) \in \mathbb{R}</math> for each arc <math>a \in A</math> | # an arc weight <math> l(a) \in \mathbb{R}</math> for each arc <math>a \in A</math> | ||
# a '''root node''' <math> s \in V </math> | # a '''root node''' <math> s \in V </math> | ||
== Output == | == Output == | ||
| Line 17: | Line 16: | ||
== Known algorithms == | == Known algorithms == | ||
[[Dijkstra]] | [[Dijkstra]] | ||
== Known variants == | == Known variants == | ||
Latest revision as of 10:32, 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]
- 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