Dÿkstra's Algorithm

Single Source Shortest Path and Greedy Algorithms continued: Dÿkstra's Algorithm

Example 1 - Find length of shortest path:                                          a to z. Start at a a → a = 0 a → b = 4  or a → d = 2 a → d → e = 5  or a → b = 4 a → b → e = 7  or a → b → c = 7  or a → d → e = 5 a → b → e = 7  or a → b → c = 7  or a → d → e → z = 6

Question 24.6.1 Find length of shortest path:                      s to x. Start at c s → s = 0

Single Source Shortest Path for Cyclic graph 

Consider a weighted, directed graph G = (V, E, w)

• V is the set of vertices.
• E is the set of edges that are order pairs linking the vertices.
• w is a function from E to the real numbers giving the weight of an edge.

For example, in the following graph we have:

• V = { s, x, y, z }
• E = { (s,x), (s,y), (x,y), (y,x), (y,z), (z,x) }
• w

  w	s	x	y	z
  s	∞	10	5	∞
  x	∞	∞	3	∞
  y	∞	4	∞	1
  z	∞	2	∞	∞

In a practical application, the graph might represent cities and distances between them in terms of airplane ticket cost, road miles, or some other metric.

Another example would be Internet nodes connected by transmission lines of different speeds.

 

A path through the graph is a sequence of vertices that are connected by edges.

Example: (s, x, y, z) is a path connecting vertex s to vertex z.

The length or cost of a path is the sum of all the weights of the edges traversed.

Example: The length of (s, x, y, z)  is w(s, x) + w(x, y) + w(y, z) = 10+3+1=14.

Another path is (s, y, z), with length 5+1=6, so some paths are longer and shorter than others.

Single-Source Shortest Paths for Cyclic graph

We would like to know, given a single source vertex, the length of the shortest path to any other vertex.

It can be solved with a greedy algorithm called Dÿkstra's Algorithm.

Key data are:

• V : the vertices G(V).
  
• v.d : array tracks the current minimum distances

  At any point in the algorithm, v.d is the current minimum length of a path from source vertex to vertex v.
  

• Q : priority queue (heap) that contains vertices whose priorities are their values in d (smaller value means higher priority).

Note that the priority queue must be able to automatically account for adjustments to d.
Assume the Q is updated with each access of d.

• v.π : predecessor array

Dÿkstra's Algorithm

No negative-weight edges.

Essentially a weighted version of breadth-first search.

• Instead of a FIFO queue as in BFS, uses a priority queue (e.g. min-heap).
• Values of heap are shortest-path weights, v.d

Have two sets of vertices:

• S = vertices whose final shortest-path weights are determined, these are colored yellow below.
• Q = priority queue = V − S (all vertices minus those having final weights determined).

Example

1) Init-Single-Source(V, s)   s x y z π NIL NIL NIL NIL d 0 ∞ ∞ ∞ Q   s x y z S = | 0 ∞ ∞ ∞	2)   s x y z π NIL s s NIL d 0 10 5 ∞ Q u=s y x z S = { s } 5 10 ∞
3)   s x y z π NIL y s y d 0 9 5 6 Q u=y z x S = { s, y } 6 9	4)   s x y z π NIL z s y d 0 8 5 6 Q u=z x S = { s, y, z } 8
5)   s x y z π NIL z s y d 0 8 5 6 Q = ∅ u=x x S = { s, y, z, x } 8

Question 24.6.2

• Does the algorithm find the shortest part to a destination or to all reachable destinations?
• Where's the greed?
• S is constructed but never used. What is the purpose of S?
• From the graph at right, give a source vertex for producing an S ≠ V.
• There is a cycle (y, x, y). How is looping on cycles prevented?
• Why are negative weights excluded?

Analysis

An analysis of Dÿkstra's Algorithm depends heavily on the particular implementation of graphs and the priority queues.

If we know that there are very few edges, an adjacency list representation would be more appropriate.

We'll assume a matrix representation for the analysis.

Adjacency matrix representation

w array access is Θ(1) when Q is a queue of array indices; for example, w(s, x) = 10.

Storage for an adjacency matrix is Θ(n²).

w   s x y z s ∞ 10 5 ∞ x ∞ ∞ 3 ∞ y ∞ 4 ∞ 1 z ∞ 2 ∞ ∞

Analysis: O((E+V) lg V)

Using a heap-based priority queue call Heapify each time Q changes which happens O(|Q|) times throughout the while loop and takes O(lg |Q|) time for each call Heapify.

O(|Q| lg |Q|) or O(|V| lg |V|) since Q=V.

The initialization of d is Θ(|V|).

The initialization of the queue is O(|V|).

The while loop iterates |V| times.

Extract-Minimum each time through the while loop, each Heapify cost O(lg |V|) time.

O(|V| lg |V|)

No edge is considered more than once for each edge for loop, so |E| is an upper bound on the number of possible updates to d and thus calls to Heapify, which each cost O(lg |V|) time.

O(|E| lg |V|)

So the algorithm runs in time:

O(|V|) at Line 1 and 3 for initializing, the queue (heap) +

O(|V| lg |V|) at Line 5 for the |V| calls to Extract-Minimum's (from heap) +

O((|E|+|V|) lg |V|) at Line 8, each Relax requires Heapify to update an edge for d

= max (O(|V|), O(|V| lg |V|), O((|E|+|V|) lg |V|))

= O((|E|+|V|) lg |V|)

 

	Dÿkstra(V, E, w, s)
1	Init-Single-Source(V, s)	Θ(|V|)
2	S ← ∅	Θ(1)
3	Q ← V	O(|V|)
4	while Q ≠ ∅ do	O(|V|)
5	u ← Extract-Min( Q )	O(|V| lg |V|)
6	S ← S ∪ { u }	Θ(1)
7	for each vertex v ∈ Adj[ u ]	O(|E|+|V|)
8	do Relax(u, v, w)	O((|E|+|V|) lg |V|)