Single source shortest paths: Difference between revisions

From Algowiki
Jump to navigation Jump to search
(Replaced content 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> # a '''root node''' <math> s \in V...")
No edit summary
Line 7: Line 7:


== Output ==
== 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>
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 ==
== Objective ==
N/A
N/A


== Complexity ==
== Complexity ==
Polynomial
Polynomial


== Known algorithms ==
== Known algorithms ==

Revision as of 10:30, 20 October 2014

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


Known variants