15-451 March 7, 2006
Breadth First Search, Shortest paths,
and Minimum Spanning Trees (MST)
Daniel Sleator
----------------------------------------------------
Announcements
Midterm Exam Thursday, March 9.
All material up to and including this lecture.
Review session tomorrow in recitaiton.
----------------------------------------------------
Today's lecture:
Breadth-First-Search (BFS) and shortest paths
Basic generic algorithm
Dijkstra's algorithm
Minimum Spanning Trees
Prim's algorithm
Kruskal's algorithm
Proofs of correctness
See sections 4.4 and 4.5 of Kleinberg-Tardos
--------------------------------------------
Breadth-First-Search (BFS)
-------------------------
Last time we talked about DFS. An alternative way to search
a graph is Breadth-First-Search. Here's pseudo-code for
BFS starting from a special source vertex s. We maintain
two sets of vertices Completed (C), and Frontier (F).
C = {}
F = {s}
while (F is not empty) {
F' = {}
for each v in F do {
for each w in adj(v) do {
if (w not in C and w not in F) F' = F' union w
}
}
C = C union F
F = F'
}
Theorem: This algorithm eventually explores all the vertices
reachable from s.
An alternative implementation of this algorithm uses a
queue. (Described below in the context of shortest paths.)
Shortest Paths
--------------
Unweighted shortest path problem: Given an undirected graph
G, and a special node s (call it "the source"), find the
shortest path in G from s to all other vertices.
[The shortest path from s to t is the path starting at s and
ending at t with the fewest edges.]
We can adapt the above BFS algorithm to this problem.
The algorithm is the same, except we maintain a distance
field for each vertex in the graph.
C = {}
F = {s}
d = 0
s.distance = 0
while (F is not empty) {
F' = {}
for each v in F do {
for each w in adj(v) do {
if (w not in C and w not in F) {
F' = F' union w
w.distance = d+1
}
}
}
C = C union F
F = F'
d++
}
Theorem: When the algorithm terminates the distance field of
each vertex v reachable from s has been assigned the
shortest path length from s to v.
Proof: There's an invariant that holds at the beginning of
the loop. Here it is:
Invariant: The distance fields of all vertices in C
and F are the shortest path distances to these vertices.
These are all the vertices with distance d or less.
It's easy to see that this holds initially. Let's prove
it's preserved in each iteration of the loop.
Consider a vertex w that's about to be added to F'. Its
distance cannot be d or less, because it would have been
in F or C. And there is a path from s to w of distance
d+1. Therefore its shortest path distance is d+1.
How do we know we've found all vertices at distance d+1?
Well, any vertex at distance d+1 must have a vertex at
distance d on its shortest path. And this algorithm
explores all of these.
[Note, we can replace
w.distance = d+1
by
w.distance = v.distance+1
and eliminate d from the algorithm.]
Here's an alternative implementation using a FIFO queue. Q.
C = {}
Q = {s}
s.distance = 0
while (Q is not empty) {
v = Q.remove()
for each w in adj(v) do {
if (w not in C and not in Q) {
Q.add(w)
C = C union w.
w.distance = v.distance+1
}
}
}
Dijkstra's algorithm
--------------------
We generalize the situation to the case where each edge has
a length associated with it. So if edge e = (u,v) then
let l(u,v) denote the length of this edge.
Suppose that all the lengths are non-negative. Dijkstra's
algorithm finds the shortest paths from a source vertex to
all other vertices.
Here's the algorithm as described by Kleinberg-Tardos.
G is a graph (V,E), l are the lengths.
(we've used d(v) instead of v.distance)
(s is the source vertex)
Dijkstra(G,l)
For each u in V d(u) = infinity
C = {s}
d(s) = 0
while C != V do
Select a node v not in C for which there is an edge
from a node in C to v, and such that
d'(v) = MIN d(u) + l(u,v)
(u,v) in E
u in C
is as small as possible.
Add v to C, and define d(v) = d'(v)
After running this algorithm, the distance labels d() are
the length of the shortest paths from s. (Proof below.)
If we want to reconstruct these shortest paths, we can do this as
follows. As each vertex v is added to C, we also remember the edge
(u,v) which minimized d'(v). With this extra information, we can find
our way back back from any vertex v all the way to s, via a path whose
length is d(v). Call this path P_v.
The following fact is the key to why the algorithm
works:
Lemma: At the beginning of the while loop, for any u in C,
the path P_u is a shortest s-u path
Proof: The proof is by induction on the size of C.
Certainly it's true at the beginning, when C={s}.
Now we suppose the lemma is true before we add a new vertex v to C.
Let u be the vertex before v on its path. We know that u was in C
before, so by induction, the path P_u was a shortest path. Could
there be some other path from s to v that is shorter? Consider any
such path P. That path starts in C. It must eventually leave C.
Let x be the next vertex it comes to after leaving C. The length of
the path from s to x must already be at least as large as d(v) ---
because when we picked v we considered this option, and rejected it in
favor of v. Because the edges are non-negative in length, the rest of
the path P from x to v just add more to its length. Thus P cannot be
shorter than the path found by the algorithm. QED.
This algorithm can be efficiently implemented using a priority queue
data structure. Say we have a priority queue API that supports the
following operations. Each node has a distance field which is used
as the priority by the queue.
This makes use of a priority queue with the following API:
PQ.insert(node)
Insert a new node into the priority queue with
priority node.distance
PQ.decreasePriority(node)
Assuming the given node is already in the
priority queue, decrease its priority
to node.distance
PQ.deletemin()
Delete the node of minimum key and return it.
Dijkstra() {
C = {}
PQ = new PriorityQueue()
s.inqueue = true
s.distance = 0
PQ.insert(s)
while (PQ is not empty) {
v = PQ.deletemin()
v.inqueue = false
C = C union v
for each w in adj(v) do {
if (w not in C) {
if (w.inqueue) {
if ((w.distance > v.distance + l(v.w)) {
w.distance = v.distance + l(v.w)
PQ.decreasePriority(w)
}
} else {
w.distance = v.distance + l(v.w)
PQ.insert(w)
w.inqueue = true
}
}
}
}
}
[Draw pictures to illustrate what this is doing]
[Run through an example]
Before we prove that this works, let's look at the running
time.
The code (excluding the priority queue operations) is like BFS.
It's O(n+m). O(edges + vertices).
What about the PQ operations? Well, there are at most n
inserts and at most n deletemins, and there are at most m
decrease keys. If all of these are O(log n) then the
algorithm is
O((n+m) log n)
Theorem: The priority queue implementataion of Dijkstra's algorithm
computes the shortest path distance from s to all other vertices.
Proof:
The proof is a little more complicated, because we have to talk about
what the distance fields for all the nodes in the priority queue mean.
Let PQ be the set of vertices in the priority queue. Here is the
invariant that holds at the beginning of the while loop:
Invariant: C and PQ are disjoint
For all vertices in C the shortest path distance has
been computed.
For all vertices v in PQ the distance field is the
length of the shortest path that starts from s, uses
any number of vertices in C, followed by an edge from C
to v.
Explain why this is preserved.
QED.
Alternative explanation of Dijkstra's algorithm where we
replace an edge of length l(u,v) by l(u,v) unit length
edges.
Minimum Spanning Trees
----------------------
Consider a connected undirected graph G where each edge e
has a cost c(e).
A spanning tree of this graph is simply a subgraph of G that
is a tree and has al the vertices of G.
The minimum spanning tree is simply the spanning tree of
minimum total cost.
Before we start, there's an important property of spanning
trees that we'll make use of:
Fact: Suppose we have a spanning tree t of a graph G. The
operation of adding an edge to t creates a subgraph t' of G that
has exactly one cycle. Now if any edge on this cycle is removed
this produces a new spanning tree t' of G.
Proof: Last time we showed: Theorem: an undirected connected
graph is a tree if and only if it has n-1 edges. By adding an
edge to a tree, it now has n edges. It's still connected, so it
must have a cycle. Now deleting any edge on the cycle preserves
connectivity. The new graph t' therefore must also be a tree.
QED.
First I'll present a very general algorithm called "The Red Rule"
for computing a spanning tree, then prove that the Red Rule
computes a MST. Later I'll give two algorithms for the MST
problem that work by virtue of being implementations of the
red rule.
The Red Rule: Repeatedly color edges red according to the
following criterion, until the red edges form a spanning tree.
Partition the graph into two sets of vertices A and V-A such
that there are no red edges between them. Pick the minimum
cost edge that connects A to V-A. Color it red.
Theorem: The red rule computes a MST.
Proof: First of all, the Red Rule cannot create a cycle. (why?)
So when there are n-1 red edges, the red edges form a spanning
tree.
The induction hypothesis we'll use is the following:
At any point in the algorithm, there exists a minimum
spanning tree T such that T contains all the red edges.
Clearly this is true when we start, because there are no red
edges. So any MST can be T in the Induction Hypothesis.
Say the IndHyp is true at iteration i. Let's prove it for i+1.
Say we have partitioned the graph into A and V-A and we're about
to color an edge e=(u,v) red.
By the IndHyp there's a MST T that contains all the red
edges. If T contains the new edge e, then the IndHyp is
preserved by coloring e red. So suppose T does not contain
edge e. Here's a picture.
____________ ___________
| | e | |
| .------------------. |
| | | |
| A | | V-A |
| | | |
| | | |
| | | |
____________ ___________
If we add e to tree T, then this edge must form a cycle. Walk
around this cycle starting from the A side of e and traversing e.
Eventually this walk must take us back from V-A to A. Call this
edge e'. e' cannot be colored red, because the way we chose A
was that there must be no red edges from A to V-A. So modify T
to produce T' by removing e from T and adding e' to it. The
new tree T' is a spanning tree. Now note:
C(T') = C(T) + c(e) - c(e')
But by the red rule, c(c) <= c(e'), cause e was the minimum
cost edge crossing the cut. Therefore C(T') <= C(T).
So if T was a MST, so is T'. Thus the IndHyp is preserved
with T'.
QED.
Prim's Algorithm
----------------
The algorithm just grows a MST from a start vertex s, by
always choosing the minimum cost edge from the current
tree to some vertex not in the tree.
The algorithm is just like Dijkstra's algorithm
with a couple of tiny tweeks.
Prim() {
C = {}
PQ = new PriorityQueue()
s.inqueue = true
s.distance = 0
s.predecessor = null
PQ.insert(s)
while (PQ is not empty) {
v = PQ.deletemin()
v.inqueue = false
C = C union v
print "edge (v.predecessor, v) is in the MST"
for each w in adj(v) do {
if (w not in C) {
if (w.inqueue) {
if ((w.distance > l(v.w)) {
w.distance = l(v.w)
w.predecessor = v
PQ.decreasePriority(w)
}
} else {
w.distance = l(v.w)
w.predecessor = v
PQ.insert(w)
w.inqueue = true
}
}
}
}
}
Note that we've added a predecessor field to keep track of
the vertex that "caused us to be added to the PQ".
The running time is the same as Dijkstra's algorithm.
Correctness is simply based on the fact that it's a valid
implementation of the red coloring rule. The cut in
question is simply the vertices in the tree so far versus
all the other vertices in the graph.
Kruskal's MST algorithm
-----------------------
There's a very elegant way to compute the MST using sorting
and the union/find algorithm.
Initialize the disjoint set data structure with
the universe U of all vertices of the graph.
Foreach edge e=(u,v) in increasing order of cost do {
if (Find(u) != Find(v)) {
Union(u,v)
print (u,v)
}
}
It's also easy to show this is an implementatin of the red
rule.