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.
Smallest Key
log(n)
levels
0
1
3
7
5
8
6
Insert
Add key at bottom
Bubble up
O(log(n)) time
0
1
3
7
5
8
6
4
4
6
4
5
Decrease Key
Change Key
Bubble up
O(log(n)) time
0
1
7
4
8
5
3
6
2
2
4
DeleteMin
Remove & Return root node
Move bottom to top
Bubble down
Runtime O(log(n))
Output:
0
1
3
7
2
4
5
6
0
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?
Yes
No
1
2
-100
0
1
2
Length = -98
s
t
What Goes Wrong
Correctly Assigned Distances
ℓ(v,w)
dist(v)
ℓ(v’,w’)
dist(v’)
P
dist(v) + ℓ(v,w) ≤ dist(v’) + ℓ(v’,w’)
+ ℓ(P)
Doesn’t work if ℓ(P) is negative!
s
v
w
w’
v’
Problem
What is the shortest path length from s to t?
1
1
-1
-1
Length:
1
-1
-3
As small as we like
s
t
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
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.
s
w
v
Algorithm Idea
Instead of finding shortest paths (which may not exist), find shortest paths of length at most k.
distk-1(v)
ℓ(v,w)
k-1 edges
s
w
v
Algorithm
Bellman-Ford(G,s,ℓ)
dist0(v) ← ∞ for all v
//cant reach
dist0(s) ← 0
For k = 1 to n
For w ∈ V
distk(w)←min(distk-1(v)+ℓ(v,w))
distk(s) ← min(distk(s),0)
// s has the trivial path
O(|E|)
What value of k do we use?
Example
1
2
1
1
-2
k:
0
0
∞
∞
∞
1
1
2
2
0
2
3
1
4
Stabalizes
s
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
Non-negative total weight
(no negative weight cycles)
Remove other cycles until none left
At most |V|-1 edges
s
t