Announcements
Announcements
• Homework 2 Due on Friday
• Exam 1 Solutions Online
• Exam grades soon
Last Time
• Shortest Paths in Weighted Graphs
• Priority Queue
– Insert
– DeleteMin
– DecreaseKey
– Saw Binary Heap
• Dijkstra’s Algorithm
– Runtime O(|V|)(Inserts/DeleteMins)+O(|E|)DecreaseKeys
– O(log|V|(|V|+|E|)) w/ binary heap
Binary Heap
Store elements in a balanced binary tree with
each element having smaller key than its
children.
0
1
3 7
5
8 6
Smallest Key
log(n)
levels
Insert
0
1
3 7
5
8 6
• Add key at bottom
• Bubble up
O(log(n)) time
4
4
6
4
5
Decrease Key
0
1
7
4
8 5 3
6
• Change Key
• Bubble up
O(log(n)) time
2
2
4
DeleteMin
0
1
3 7
2
4 5
6 • Remove & Return root node
• Move bottom to top
• Bubble down
Runtime O(log(n))
0
Output: 6
6
1
6
3
Today
• A few more priority queues
• Negative edge weights
d-ary Heap
• Like binary heap, but each node has d children
• Only log(n)/log(d) levels.
• Bubble up faster!
• Bubble down slower – need to compare to
more children.
Summary
Runtime:
• Insert – O(log(n)/log(d))
• DecreaseKey – O(log(n)/log(d))
• DeleteMin – O(dlog(n)/log(d))
• Dijkstra – O(log|V|(d|V|+|E|)/log(d))
Fibonacci Heap
• Advanced data structure.
• Uses amortization.
Runtime:
• Insert – O(1)
• DecreaseKey – O(1)
• DeleteMin – O(log(n))
• Dijkstra – O(|V|log|V|+|E|)
Summary of Priority Queues
Negative Edge Weights
• So far we have talked about the case of non-
negative edge weights.
– The usual case (distance & time usually cannot be
negative).
– However, if “lengths” represent other kinds of
costs, sometimes they can be negative.
• Problem statement same. Find path with
smallest sum of edge weights.
Question: Dijkstra for Negative
Edge Weights
Does Dijkstra’s algorithm work in graphs with
negative edge weights?
A) Yes
B) No
s
t
1
2
-100 0
1
2 Length = -98
What Goes Wrong
s
Correctly Assigned Distances
v
w ℓ(v,w)
dist(v)
w’
v’
ℓ(v’,w’)
dist(v’)
P
dist(v) + ℓ(v,w) ≤ dist(v’) + ℓ(v’,w’) + ℓ(P)
Doesn’t work if ℓ(P) is negative!
Problem
What is the shortest path length from s to t?
s t
1 1
-1
-1
Length: 1 -1 -3
As small as
we like
Negative Weight Cycles
Definition: A negative weight cycle is a cycle
where the total weight of edges is negative.
• If G has a negative weight cycle, then there
are probably no shortest paths.
– Go around the cycle over and over.
• Note: For undirected G, a single negative
weight edge gives a negative weight cycle by
going back and forth on it.
Fundamental Shortest Paths
Formula
s w
v dist(v) ℓ(v,w)
• System of equations to solve for distances.
• When ℓ ≥ 0, Dijsktra gives an order to solve in.
• With ℓ < 0, might be no solution.
Algorithm Idea
Instead of finding shortest paths (which may not
exist), find shortest paths of length at most k.
s w
v distk-1(v)
ℓ(v,w)
k-1 edges
Algorithm
Bellman-Ford(G,s,ℓ)
dist
0
(v) ← ∞ for all v
//cant reach
dist
0
(s) ← 0
For k = 1 to n
For w ∈ V
dist
k
(w)←min(dist
k-1
(v)+ℓ(v,w))
dist
k
(s) ← min(dist
k
(s),0)
// s has the trivial path
O(|E|)
What value of k
do we use?
Example
s
1
2
1
1
-2
k: 0
0
∞
∞
∞
1
1
2 2
0 2
3
1
4
Stabalizes
Analysis
Proposition: If n ≥ |V|-1 and if G has no
negative weight cycles, then for all v,
dist(v) = distn(v).
• If there is a negative weight cycle, there
probably is no shortest path.
• If not, we only need to run our algorithm for
|V| rounds, for a final runtime O(|V||E|).
Proof
• We need to show that the shortest path has
fewer than |V| edges.
• If a path has at least |V| edges, it must
contain the same vertex twice (by the
pigeonhole principle).
• This means it has a loop.
• Removing the loop gives a shorter path.
Proof
s
t
Non-negative total weight
(no negative weight cycles)
Remove
other cycles
until none
left
At most |V|-1 edges