Dijkstra ALGO PPT DETAILED DOCUMENTATION

Dijkstra ALGO PPT DETAILED DOCUMENTATION

1. Dijkstra’s Algorithm
Slide Courtesy: UT
1

2. Single-Source Shortest Path Problem
Single-Source Shortest Path Problem - The
problem of finding shortest paths from a source
vertex v to all other vertices in the graph.

3. Applications
- Maps (Map Quest, Google Maps)
- Routing Systems

4. Dijkstra's algorithm
Dijkstra's algorithm - is a solution to the single-source
shortest path problem in graph theory.
 
 
Works on both directed and undirected graphs. However,
all edges must have nonnegative weights.
Input: Weighted graph G={E,V} and source vertex v∈V,
such that all edge weights are nonnegative
 
Output: Lengths of shortest paths (or the shortest paths
themselves) from a given source vertex v∈V to all other
vertices

5. Approach
•The algorithm computes for each vertex u the distance to u from
the start vertex v, that is, the weight of a shortest path between
v and u.
•the algorithm keeps track of the set of vertices for which the
distance has been computed, called the cloud C
•Every vertex has a label D associated with it. For any vertex u,
D[u] stores an approximation of the distance between v and u.
The algorithm will update a D[u] value when it finds a shorter
path from v to u.
•When a vertex u is added to the cloud, its label D[u] is equal to
the actual (final) distance between the starting vertex v and
vertex u.
5

6. Dijkstra pseudocode
Dijkstra(v1, v2):
for each vertex v: // Initialization
v's distance := infinity.
v's previous := none.
v1's distance := 0.
List := {all vertices}.
while List is not empty:
v := remove List vertex with minimum distance.
mark v as known.
for each unknown neighbor n of v:
dist := v's distance + edge (v, n)'s weight.
if dist is smaller than n's distance:
n's distance := dist.
n's previous := v.
reconstruct path from v2 back to v1,
following previous pointers.
6

7. Dijkstra’s Pseudo Code
•Graph G, weight function w, root s
relaxing
edges
O(v) +O(v)
VlogV
ElogV

8. 8
Example: Initialization
A
GF
B
EC D
4 1
2
103
64
22
85
1
0
∞

∞

∞

∞
Pick vertex in List with minimum distance.

∞

∞
Distance(source) = 0 Distance (all vertices
but source) =
∞

9. 9
Example: Update neighbors'
distance
A
GF
B
EC D
4 1
2
103
64
22
85
1
0 2

∞

∞
1

∞

∞
Distance(B) = 2
Distance(D) = 1

10. 10
Example: Remove vertex with
minimum distance
Pick vertex in List with minimum distance, i.e., D
A
GF
B
EC D
4 1
2
103
64
22
85
1
0 2

∞

∞
1

∞

∞

11. 11
Example: Update neighbors
A
GF
B
EC D
4 1
2
103
64
22
85
1
0 2
3
3
1
9 5
Distance(C) = 1 + 2 = 3
Distance(E) = 1 + 2 = 3
Distance(F) = 1 + 8 = 9
Distance(G) = 1 + 4 = 5

12. 12
Example: Continued...
A
GF
B
EC D
4 1
2
103
64
22
85
1
0 2
3
3
1
Pick vertex in List with minimum distance (B) and update neighbors
9 5
Note : distance(D)

not
updated since D is
already known and
distance(E) not updated
since it is larger than
previously computed

13. 13
Example: Continued...
A
GF
B
EC D
4 1
2
103
64
22
85
1
0 2
3
3
1
9 5
No updating
Pick vertex List with minimum distance (E) and update neighbors

14. 14
Example: Continued...
A
GF
B
EC D
4 1
2
103
64
22
85
1
0 2
3
3
1
8 5
Pick vertex List with minimum distance (C) and update neighbors
Distance(F) = 3 + 5 = 8

15. 15
Example: Continued...
A
GF
B
EC D
4 1
2
103
64
22
85
1
0 2
3
3
1
6 5
Distance(F) = min (8, 5+1) = 6
Previous distance
Pick vertex List with minimum distance (G) and update neighbors

16. 16
Example (end)
A
GF
B
EC D
4 1
2
103
64
22
85
1
0 2
3
3
1
Pick vertex not in S with lowest cost (F) and update neighbors
6 5

17. Another Example

18. Another Example

19. Another Example

20. Another Example

21. Another Example

22. Another Example

23. Another Example

24. Another Example

25. Another Example

26. THE KNOWN
CLOUD
v
P: Next shortest path from
inside the known cloud
v'
Correctness :“Cloudy” Proof
•If the path to v is the next shortest path, the path to v' must be at
least as long. Therefore, any path through v' to v cannot be shorter!
Source
Least cost node
competitor
When a vertex is added to the cloud, it has shortest
distance to source.

27. 27
Dijkstra’s Correctness
•We will prove that whenever u is added to S, d[u] =
(s,u), i.e., that d[u] is minimum, and that equality is
maintained thereafter
•Proof
–Note that v, d[v] ≥ (s,v)
–Let u be the first vertex picked such that there is a shorter
path than d[u], i.e., that d[u]  (s,u)
–We will show that this assumption leads to a contradiction

28. 28
Dijkstra Correctness (2)
•Let y be the first vertex V – S on the actual
shortest path from s to u, then it must be that d[y] =
(s,y) because
–d[x] is set correctly for y's predecessor x S on the
shortest path (by choice of u as the first vertex for which d
is set incorrectly)
–when the algorithm inserted x into S, it relaxed the edge
(x,y), assigning d[y] the correct value

29. 29
•But if d[u] > d[y], the algorithm would have chosen y
(from the Q) to process next, not u  Contradiction
•Thus d[u] = (s,u) at time of insertion of u into S, and
Dijkstra's algorithm is correct
Dijkstra Correctness (3)
[ ] ( , ) (initial assumption)
( , ) ( , ) (optimal substructure)
[ ] ( , ) (correctness of [ ])
[ ] (no negative weights)
d u s u
s y y u
d y y u d y
d y
 
  
 


30. 30
Time Complexity: Priority Queue
For sparse graphs, (i.e. graphs with much less than |V
2
| edges)
Dijkstra's implemented more efficiently by priority queue
•Initialization O(|V|) using O(|V|) buildHeap
•While loop O(|V|)
•Find and remove min distance vertices O(log |V|) using O(log |V|)
deleteMin
•Potentially |E| updates
•Update costs O(log |V|) using decreaseKey
Total time O(|V|log|V| + |E|log|V|) = O(|E|log|V|)
•|V| = O(|E|) assuming a connected graph

31. 31
B
C
A
10
-3
5
B
C
A
10
-8
5
Working
Not Working

32. 32
Shortest Path Problems
•How can we find the shortest route between two
points on a road map?
•Model the problem as a graph problem:
–Road map is a weighted graph:
vertices = cities
edges = road segments between cities
edge weights = road distances
–Goal: find a shortest path between two vertices (cities)

33. 33
Shortest Path Problem
•Input:
–Directed graph G = (V, E)
–Weight function w : E → R
•Weight of path p = v
0, v
1, . . . , v
k
•Shortest-path weight from u to v:
δ(u, v) = min w(p) : u v if there exists a path from u to v
∞ otherwise
•Note: there might be multiple shortest paths from u to v



k
i
iivvwpw
1
1),()(
p
0
3 9
5 11
3
6
5
7
6
s
t x
y z
2
2 1
4
3

34. 34
Variants of Shortest Path
•Single-source shortest paths
–G = (V, E)  find a shortest path from a given
source vertex s to each vertex v  V
•Single-destination shortest paths
–Find a shortest path to a given destination vertex t
from each vertex v
–Reversing the direction of each edge  single-
source

35. 35
Variants of Shortest Paths (cont’d)
•Single-pair shortest path
–Find a shortest path from u to v for given vertices
u and v
•All-pairs shortest-paths
–Find a shortest path from u to v for every pair of
vertices u and v

36. 36
Negative-Weight Edges
•Negative-weight edges may form negative-
weight cycles
•If such cycles are reachable from
the source, then δ(s, v) is not properly
defined!
–Keep going around the cycle, and get
w(s, v) = -  for all v on the cycle
0
3
-4
2
8
-6
s
a b
e f
-3
y
3
5
6
4
7
c d g

37. 37
Negative-Weight Edges
•s  a: only one path
δ(s, a) = w(s, a) = 3
•s  b: only one path
δ(s, b) = w(s, a) + w(a, b) = -1
•s  c: infinitely many paths
s, c, s, c, d, c, s, c, d, c, d, c
cycle has positive weight (6 - 3 = 3)
s, c is shortest path with weight δ(s, b) = w(s, c) = 5
0
3 -1
- -
3
-4
2
8
-6
s
a b
e f
-5 11
-3
y
3
5
6
4
7
c d g

38. 38
Negative-Weight Edges
•s  e: infinitely many paths:
–s, e, s, e, f, e, s, e, f, e, f, e
–cycle e, f, e has negative
weight:
3 + (- 6) = -3
–can find paths from s to e with
arbitrarily large negative weights
–δ(s, e) = -   no shortest path
exists between s and e
–Similarly: δ(s, f) = - ,
δ(s, g) = - 
0
3 -1
- -
3
-4
2
8
-6
s
a b
e f
-5 11
-3
y
3
5
6
4
7
c d g
 

j
h i
2
3-8
δ(s, h) = δ(s, i) = δ(s, j) = 
h, i, j not
reachable
from s

39. 39
Cycles
•Can shortest paths contain cycles?
•Negative-weight cycles
–Shortest path is not well defined
•Positive-weight cycles:
–By removing the cycle, we can get a shorter path
•Zero-weight cycles
–No reason to use them
–Can remove them to obtain a path with same weight
No!
No!

40. 40
Optimal Substructure Theorem
Given:
–A weighted, directed graph G = (V, E)
–A weight function w: E  R,
–A shortest path p = v
1, v
2, . . . , v
k from v
1 to v
k
–A subpath of p: p
ij
= v
i
, v
i+1
, . . . , v
j
, with 1  i  j  k
Then: p
ij
is a shortest path from v
i
to v
j
Proof: p = v
1
v
i
v
j
v
k
w(p) = w(p
1i
) + w(p
ij
) + w(p
jk
)
Assume  p
ij
’ from v
i
to v
j
with w(p
ij
’) < w(p
ij
)
 w(p’) = w(p
1i
) + w(p
ij
’) + w(p
jk
) < w(p) contradiction!
p
1i p
ij p
jk
v
1
v
i
v
j
v
k
p
1i
p
ij
p
ij
’
p
jk

41. 41
Triangle Inequality
For all (u, v)  E, we have:
δ (s, v) ≤ δ (s, u) + δ (u, v)
- If u is on the shortest path to v we have the
equality sign
u v
s
v
s
u

42. 42
Algorithms
•Bellman-Ford algorithm
–Negative weights are allowed
–Negative cycles reachable from the source are not
allowed.
•Dijkstra’s algorithm
–Negative weights are not allowed
•Operations common in both algorithms:
–Initialization
–Relaxation

43. 43
Shortest-Paths Notation
For each vertex v  V:
•δ(s, v): shortest-path weight
•d[v]: shortest-path weight estimate
–Initially, d[v]=∞
–d[v]δ(s,v) as algorithm progresses
•[v] = predecessor of v on a shortest
path from s
–If no predecessor, [v] = NIL
– induces a tree—shortest-path tree
0
3 9
5 11
3
6
5
7
6
s
t x
y z
2
2 1
4
3

44. 44
Initialization
Alg.: INITIALIZE-SINGLE-SOURCE(V, s)
1. for each v  V
2. do d[v] ← 
3. [v] ← NIL
4.d[s] ← 0
•All the shortest-paths algorithms start with INITIALIZE-
SINGLE-SOURCE

45. 45
Relaxation Step
•Relaxing an edge (u, v) = testing whether we can
improve the shortest path to v found so far by
going through u
If d[v] > d[u] + w(u, v)
we can improve the shortest path to v
 d[v]=d[u]+w(u,v)
 [v] u
←
5 9
2
u v
5 7
2
u v
RELAX(u, v, w)
5 6
2
u v
5 6
2
u v
RELAX(u, v, w)
After relaxation:
d[v]  d[u] + w(u,
v)
s s
no change

46. 46
Bellman-Ford Algorithm
•Single-source shortest path problem
–Computes δ(s, v) and [v] for all v  V
•Allows negative edge weights - can detect
negative cycles.
–Returns TRUE if no negative-weight cycles are
reachable from the source s
–Returns FALSE otherwise  no solution exists

47. 47
Bellman-Ford Algorithm (cont’d)
•Idea:
–Each edge is relaxed |V–1| times by making |V-1|
passes over the whole edge set.
–To make sure that each edge is relaxed exactly
|V – 1| times, it puts the edges in an unordered
list and goes over the list |V – 1| times.
0
 
 
6
5
7
7
9
s
t x
y z
8
-3
2
-4
-2
(t, x), (t, y), (t, z), (x, t), (y, x), (y, z), (z, x), (z, s), (s, t), (s, y)

48. 48
BELLMAN-FORD(V, E, w, s)
0
 
 
6
5
7
7
9
s
t x
y z
8
-3
2
-4
-2
0
 
 
6
5
7
7
9
s
t x
y z
8
-3
2
-4
-2
E: (t, x), (t, y), (t, z), (x, t), (y, x), (y, z), (z, x), (z, s), (s, t), (s, y)
6
7
Pass 1

49. 49
Example
0
6 
7 
6
5
7
7
9
s
t x
y z
8
-3
2
-4
-2
(t, x), (t, y), (t, z), (x, t), (y, x), (y, z), (z, x), (z, s), (s, t), (s, y)
0
6 
7 
6
5
7
7
9
s
t x
y z
8
-3
2
-4
-2
11
2
4
0
6 
7 
6
5
7
7
9
s
t x
y z
8
-3
2
-4
-2
11
2
42
0
6 
7 
6
5
7
7
9
s
t x
y z
8
-3
2
-4
-2
11
2
42
-2
Pass 1
(from
previous
slide)
Pass 2
Pass 3 Pass 4

50. 50
Detecting Negative Cycles
(perform extra test after V-1 iterations)
•for each edge (u, v)  E
• do if d[v] > d[u] + w(u, v)
• then return FALSE
• return TRUE
0 

c
s b
2
3-8
0 

c
s b
2
3-8
2
5
-3 -3 2
5
c
s b
2
3-8
-1
2
-6
Look at edge (s, b):
d[b] = -1
d[s] + w(s, b) = -4
 d[b] > d[s] + w(s, b)
1
st
pass 2
nd
pass
(s,b) (b,c) (c,s)

51. 51
BELLMAN-FORD(V, E, w, s)
1. INITIALIZE-SINGLE-SOURCE(V, s)
2. for i ← 1 to |V| - 1
3. do for each edge (u, v)  E
4. do RELAX(u, v, w)
5. for each edge (u, v)  E
6. do if d[v] > d[u] + w(u, v)
7. then return FALSE //(“Graph contains neg cycle”)
8. return TRUE
Running time: O(V+VE+E)=O(VE)
(V)
O(V)
O(E)
O(E)
O(VE)