Computer science 40 dijkstra-algorithm.ppt.pdf

Computer science algorithm

1. Edge Relaxation




u
pred(v)

w


pred(v)


Shortest path algorithms differ in
the number of times the edges are
relaxed and the order in which they
are relaxed.

2. Shortests Paths in DAGs
edges according to a topological ordering of vertices.


When the graph is a directed acyclic graph (DAG), relax

3. An Example
Topological order: s, r, y, x, z, t
s
t
z
y
r
9
∞
∞
∞
0
∞
∞
3
2
9
6
5
3
4
1
x

4. s
t
z
y
r
9
3
∞
9
0
∞
2
2
9
6
5
3
4
Relax edges 〈s, r〉, 〈s, x〉, 〈s,
t〉.
1
3
x
Topological order: s, r, y, x, z, t

5. s
t
z
y
r
9
3
7
9
0
1
1
2
2
9
6
5
3
4
Relax edges 〈r, x〉, 〈r, y〉, 〈r, z〉.
1
3
x
Topological order: s, r, y, x, z, t

6. s
t
z
y
r
9
3
7
9
0
1
0
2
2
9
6
5
3
4
Relax edge 〈y, z〉.
1
3
x
Topological order: s, r, y, x, z, t

7. s
t
z
y
r
9
3
7
9
0
7
2
2
9
6
5
3
4
Relax edge 〈x, z〉.
1
3
x
Topological order: s, r, y, x, z, t

8. Finish
s
t
z
y
r
9
3
7
8
0
7
2
2
9
6
5
3
4
Relax edge 〈z, t〉.
1
3
x
Topological order: s, r, y, x, z, t

9. Correctness
Path relaxation property: If is a shortest



The topological order guarantees that edges on every path from the
source will be relaxed in the order in which they appear on the path.
Thus, the path relaxation property is satisfied and the algorithm
works correctly.

10. Dijkstra’s Algorithm








Applicable when all edge weights are non-negative.
Greedy strategy (same as breadth-first search if all weights are 1):
...

11. How to Find the Next Closest?

12. Relaxation

13. An Example
b
d
2
7
5
4
1
4
3
4
1
5
7
0
∞
2
∞
∞
∞
∞
∞


a
e
f
s
c

14. b
d
2
7
5
4
1
4
3
4
1
5
7
0
2
5
4
2
∞
∞
∞
k
s
e
f
c
a

15. b
d
s
2
7
5
4
1
4
3
4
1
5
7
0
2
4
4
9
2
∞
∞
a
c
e
f

16. a
b
d
s
2
7
5
4
1
4
3
4
1
5
7
0
2
4
4
8
7
2
∞
e
f
c

17. a
b
d
s
2
7
5
4
1
4
3
4
1
5
7
0
2
4
4
8
7
2
∞
c
e
f

18. a
f
c
b
d
s
2
7
5
4
1
4
3
4
1
5
7
0
2
4
4
8
7
14
2
e

19. a
b
d
s
2
7
5
4
1
4
3
4
1
5
7
0
2
4
4
8
7
13
2
f
e
c

20. a
fb
d
s
2
7
5
4
1
4
3
4
1
5
7
0
2
4
4
8
7
13
2
c
e

21. Algorithm Description

22. Analysis



#operations 1 |V | |E|

23. What We’ve Learned from 228
Java
♦ Inheritance & abstraction
♦ Interface vs abstract classes
♦ Dynamic binding
♦ Method overriding
♦ Cloning, shallow vs deep copying
♦ Generic programming
♦ Wild cards
Data structures
♣ Linked lists (singly, doubly, circular)
♣ Stacks
♣ Trees (general, binary, BSTs, splay)
♣ Sets & maps
♣ Hash tables
♣ Graphs
Algorthms & Analysis
♥ Big-O
♥ Binary search
♥ Sorting
∙ Selection sort
∙ Insertion sort
∙ Mergesort
∙ Quicksort
∙ Heap sort
♥ Euclid’s GCD algorithm
♥ Infix & postfix conversions
♥ Graham’s scan
♥ BFS & DFS
♥ Topological sort
♥ Dijkstra’s algorithm