Edge Relaxation

w pred(v)

u pred(v)

Shortest path algorithms differ in

the number of times the edges are
relaxed and the order in which they
are relaxed.
 Shortests Paths in DAGs
When the graph is a directed acyclic graph (DAG), relax
edges according to a topological ordering of vertices.
 An Example
9
5
r ∞
∞ y 3
6
2
3 ∞ ∞
4
x z
s 0 9 1

t ∞

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

t 9

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

t 9

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

t 9

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

t 9

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

t 8

Topological order: s, r, y, x, z, t
Relax edge 〈z, t〉.
 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.
 Dijkstra’s Algorithm
Applicable when all edge weights are non-negative.

Greedy strategy (same as breadth-first search if all weights are 1):

...
How to Find the Next Closest?
Relaxation
 An Example

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

2
7 ∞
a
d 5
2 2
5 4
5 b 1 f
s 3
∞
0 1 7
4 e
c
4 ∞
4
 2 9
7
a
2 d 5
2 4
4
5 b 1 f
s 3
∞
0 1 7
4 e
c
4 ∞
4
 2 8
7
a
2 d 5
2 4
4
5 b 1 f
s 3
∞
0 1 7
4 e
c
4 7
4
 2 8
7
a
2 d 5
2 4
4
5 b 1 f
s 3
∞
0 1 7
4 e
c
4 7
4
 2 8
7
a
2 d 5
2 4
4
5 b 1 f
s 3
14
0 1 7
4 e
c
4 7
4
 2 8
7
a
2 d 5
2 4
4
5 b 1 f
s 3
13
0 1 7
4 e
c
4 7
4
 2 8
7
a
2 d 5
2 4
4
5 b 1 f
s 3
13
0 1 7
4 e
c
4 7
4
Algorithm Description
 Analysis

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