Single Source Shortest Path

Overview - Shortest path on a DAG

Given a weighted, directed graph

G=(V, E)

with a weight function mapping edges to a real-valued weight:

w : E → R

Weight of a path p = <v₀, v₁, ..., v_k>

          _k
w(p)=∑ w(v_i-1, v_i)
         ⁱ⁼¹

Shortest-Path weight

              | min{ w(p) : uv}    if there is a path from u to v
δ(u, v)= |
              | ∞                                otherwise

Shortest path

From vertex u to v is any path with weight w(p) = δ(u, v)

Example

Shortest path at right for (s, z) has shortest path weight δ(s, z) = 3,
{(s, x), (x, y), (y, z)}

min{ w(p) : sz} = 6-1-2 = 3

Greedy algorithms

• greedy algorithm - Shortest path problems are typically solved using a general method called a greedy algorithm. We'll examine greedy algorithms more fully later in the course but greed provides an important insight to shortest path problem that is useful to know now.
  
• greedy-choice property - Some problems have a structure such that a greedy approach is an optimal approach; problems such as these are said to have the greedy-choice property. When a "locally optimal" choice can lead to a "globally optimal" solution, the problem has this property.
  
• optimal global solution - Greedy algorithms exploit some property (a heuristic) to determine what is the optimal of the possible local choices (such as finding the least path weight) which ultimately lead to the optimal global solution (e.g. the shortest path).

Question 24.1

• What currency (coins/bills) would you expect back as change for $78.96?
  
• Does the usual method of making change, giving out the smallest number of bills or coins by counting out the largest possible currency first possess a greedy-choice property?

Representing shortest paths - essentially same as with BFS. Note there is only a single source.

predecessor subgraph G_π=(V_π, E_π) induced by π where:

• v.π is v’s predecessor.
• s is the source, s.π = NIL.
• set of vertices V_π = { v ∈ V : v.π ≠ NIL} | {s}, means there is one source s.
• set of edges E_π={(v.π, v) : v ∈ V_π - {s} } forms a tree.

Initialization

• Distance estimate to source is ∞
• Predecessor is NIL

INITIALIZE-SINGLE-SOURCE(G, s) 1 for each vertex v ∈ G.V  do 2      v.d ←∞ 3      v.π ← NIL 4 s.d ← 0 Analysis Time = Θ(V)

r s t x y z π NIL NIL NIL NIL NIL NIL d ∞ 0 ∞ ∞ ∞ ∞

Relaxation

v.d = shortest path estimate

The upper-bound on the weight of a shortest path from source s to v for each v ∈ V.

RELAX function lowers the weight upper-bound to a vertex if the new edge weight is lower than the current estimate.

The current estimate, v.d, is shortest path explored so far to the vertex.

Ensures v.d will always be the shortest path to vertex v of those paths computed so far.

Example δ(s, u) = 4 δ(s, v) = 10 w(u, v) = 3 Shorter path exists to v through u: δ(s, v) = δ(s, u) + w(u, v) = 4 + 3 = 7

Example δ(s, u) = 4 δ(s, v) = 6 w(u, v) = 3 NO shorter path exists to v through u: δ(s, v) = 6

RELAX(u, v, w) 1    if v.d > u.d + w(u, v) 2       then v.d ← u.d + w(u, v) 3                v.π ←u

Analysis Time = Θ(1)

Example - w is the weight of the edge, e.g. w(r, s) = 5. Give the result of:

• RELAX( t, z, w )
  

  RELAX(t, z, w) 1    if z.d > t.d + w(t, z) 2       then z.d ← t.d + w(t, z) 3                z.π ←t

  r s t x y z π NIL NIL s s NIL NIL t d ∞ 0 2 6 ∞ ∞ 2

Question 24.2 - w is the weight of the edge, e.g. w(r, s) = 5. Give the result of:

• RELAX( t, x, w )
  
• RELAX( t, y, w )

r s t x y z π NIL NIL s s NIL NIL d ∞ 0 2 6 ∞ ∞

24.2 Single-source shortest paths in directed acyclic graphs

The following algorithm computes the shortest path from a source to all other connected vertices of a DAG.

Topologically sorting the DAG arranges vertices in a linked list in the order reachable by following edges.

Recall that topological sorting is accomplished by:

Topological-Sort (G) 1 call DFS (G) to compute the v.f for each vertex v 2 as each vertex is finished, insert it onto the front of a linked list, last finish time is first. 3 return the linked list of vertices

After line 2, topological sort yields:
 r s t x y z

	r	s	t	x	y	z
π	NIL	r	r	t	t	t
d	1	10	2	7	5	3
f	12	11	9	8	6	4

Example: Below, the topologically sorted linked list is: r, s, t, x, y, z.

Edge weights are accumulated from the source vertex to each vertex reachable from the source, following the order in the linked list.

RELAX reduces the accumulated weight to a vertex when a lower weight path to the source is examined.

Source is vertex s Initial DAG G and weights w r s t x y z r ∞ 5 3 ∞ ∞ ∞ s ∞ ∞ 2 6 ∞ ∞ t ∞ ∞ ∞ 7 4 2 x ∞ ∞ ∞ ∞ -1 1 y ∞ ∞ ∞ ∞ ∞ -2 z ∞ ∞ ∞ ∞ ∞ ∞	Topological sort - r s t x y z INITIALIZE-SINGLE-SOURCES(G, s )   r s t x y z π NIL NIL NIL NIL NIL NIL d ∞ 0 ∞ ∞ ∞ ∞
r s t x y z   RELAX(r, s, w) 1 if s.d > r.d + w(r, s) 2     then s.d ← r.d + w(r, s) 3             s.π ←r   RELAX(r, t, w) 1 if t.d > r.d + w(r, t) 2     then t.d ← r.d + w(r, t) 3              t.π ←r   r s t x y z π NIL NIL NIL NIL NIL NIL d ∞ 0 ∞ ∞ ∞ ∞ Question 24.3 - No change from r→t or r→s.                            Why?	r s t x y z   RELAX(s, t, w) 1 if t.d > s.d + w(s, t) 2     then t.d ← s.d + w(s, t) 3             t.π ←s   RELAX(s, x, w) 1 if x.d > s.d + w(s, t) 2     then x.d ← s.d + w(s, x) 3             x.π ←s   r s t x y z π NIL NIL s s NIL NIL d ∞ 0 2 6 ∞ ∞
r s t x y z   RELAX(t, x, w) 1 if x.d > t.d + w(t, x)   RELAX(t, y, w) 1 if y.d > t.d + w(t, y) 2     then y.d ← t.d + w(t, y) 3             y.π ←t   RELAX(t, z, w) 1 if z.d > t.d + w(t, z) 2     then z.d ← t.d + w(t, z) 3             z.π ←t   r s t x y z π NIL NIL s s t t d ∞ 0 2 6 6 4	r s t x y z   RELAX(x, y, w) 1 if y.d > x.d + w(x, y) 2     then y.d ← x.d + w(x, y) 3             y.π ←x   RELAX(x, z, w) 1 if z.d > x.d + w(x, z)   r s t x y z π NIL NIL s s x t d ∞ 0 2 6 5 4
r s t x y z   RELAX(y, z, w) 1 if z.d > y.d + w(y, z) 2     then z.d ← y.d + w(y, z) 3             z.π ←y   r s t x y z π NIL NIL s s x y d ∞ 0 2 6 5 3	r s t x y z Shortest path weight: δ(u, v) = w(p) = 3 Shortest path (s, z) s → x → y → z   r s t x y z π NIL NIL s s x y d ∞ 0 2 6 5 3

 

Analysis

Similar to DFS analysis since DFS part of topological sort.

Time = Θ(V + E).

Question 24.4

How many times is Line 4 executed using the graph at right for:

• r
• t
• total for all vertices.

Explain the Θ(V + E) cost in Line 4.

3	for each vertex u taken in topologically sorted order	Θ(V)
4	for each vertex v ∈ Adj[ u ]	Θ(V+E)
5	RELAX( u, v, w )	Θ(V+E)

Greedy?

So where's the greedy nature of the algorithm?

The RELAX procedure always chooses the shorter path from the current vertex back to the source over any others that have been examined.

By repeatedly lowering the upper-bound weight v.d of all vertices, the minimum weight δ(s, v), from source s to vertex v is computed, the optimal solution.

 

Critical Path Analysis (PERT)

Related to topological sorting, critical path analysis determines the longest path in the DAG, useful for determining time required to complete some task described by the DAG (e.g. commercial construction or other complex task).

Industry makes considerable use of critical path analysis often under the acronym of PERT (Program Evaluation and Review Technique).

The longest path for critical path analysis can be implemented by negating the edge weights and running DAG-SHORTEST-PATHS.

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

Example

The following negates the edge weights of the previous example.

The longest path is the critical path, since we negated the edge weights, d should also be negated; the greatest weight (longest path) from source s is then to z. We still get the shortest path of the negated weights.

After line 2, topological sort (which does not examine weights) yields: r s t x y z

	r	s	t	x	y	z
π	NIL	r	r	t	t	t
d	1	10	2	7	5	3
f	12	11	9	8	6	4

Completing DAG-SHORTEST-PATHS on the negated weights produces the longest path.

Question 24.5

• Why are both y and z on the longest path?
• What is the longest path to s?
• What is the purpose of Line 3, taking vertices in topologically sorted order?
• How would the longest path analysis be useful in construction project assuming weights are completion times?