SSSP

SSSP	powered by FreeFind Modified:

DAG at right:

Topological sort

For the following DFS table results, mark the topological sort on the DAG.

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 - Complete 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 NIL NIL NIL NIL NIL NIL

d 0 ¥ ¥ ¥ ¥ ¥

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? r-s-x-z
There are two shortest paths to z of equal length; why did the algorithm generate that one? Visited x's adjacent vertices before y's.

	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 )

Sort: r, t, s, x, y, z

r s t x y z

p NIL r r s x x

d 0 3 2 4 5 6