SSSP

SSSP	powered by FreeFind Modified:

DAG at right:

Topological sort

r s t x y z

p NIL r r s x y

d 1 2 10 3 4 5

f 12 9 11 8 7 6

Initialization - Initialize the single source shortest path table using r as the source.

INITIALIZE-SINGLE-SOURCE(G, s)

1 for each vertex v Î V[ G ] do

2 d[ v ] ¬ ¥

3 p[v] ¬ NIL

4 d[ s ] ¬ 0

r s t x y z

p

d

Relaxation

RELAX(u, v, w)

1 if d[ v ] > d[ u ] + w(u, v)

2 then d[ v ] ¬ d[ u ] + w(u, v)

3 p[v] ¬ u

Single-source shortest paths in directed acyclic graphs

Run the DAG-SHORTEST-PATHS algorithm on the DAG at right using the topological sort. Visit adjacent vertices in alphabetical order.
What is the shortest path to z?
There are two shortest paths to z of equal length; why did the algorithm generate that one?

	DAG-SHORTEST-PATHS(G, w, s)
1	topologically sort the vertices of G
2	INITIALIZE-SINGLE-SOURCES(G, s)
3	for each vertex u taken in topologically sorted order
4	do for each vertex v Î Adj[ u ]
5	do RELAX( u, v, w )

r s t x y z

p

d