OR 215Spring 1998

Network FlowsM. Hartmann

MINIMUM COST SPANNING TREE PROBLEM II

Optimality Conditions

Prim’s Algorithm

Sensitivity Analysis
OPTIMALITY CONDITIONS

Theorem.(Cut optimality theorem) A spanning tree T* is a minimum spanning tree if and only if it satisfies the following cut optimality condition:

  • For every tree arc (i,j)  T*, cij ckl for every arc (k,l) contained in the cut formed by deleting arc (i,j) from T*.

Theorem.(Path optimality theorem) A spanning tree T* is a minimum spanning tree if and only if it satisfies the following path optimality condition:

  • For every non-tree arc (k,l) of G, cij ckl for every arc (i,j) contained in the path of T* connecting nodes k and l.

Recall: The path optimality condition leads to Kruskal’s greedy algorithm.

Theorem. Let F be a subset of arcs of some minimum cost spanning tree. Let P be the set of nodes of some component of F. Let (i,j) be a minimum cost arc in the cut (P,N\P). Then F+(i,j) is a subset of arcs of some minimum cost spanning tree.

Proof: Suppose that F is a subset of the minimum cost tree T*. If (i,j)  T*, there is nothing to prove. So suppose that (i,j)  T*. Adding (i,j) to T* creates a cycle C, and C has at least on arc (k,l)  (i,j) in (P,N\P). (Why?) By assumption, cij ckl. Also, T* satisfies the cut optimality conditions, so cij ckl. It follows that cij = ckl, and that

T*+(i,j)\(k,l) is also a minimum cost spanning tree.

  • How can we take advantage of this property?
    PRIM’S ALGORITHM

Prim's algorithm grows a spanning subtree rooted at node 1, which is a subset of arcs of some minimum cost span-ning tree.

To identify the arc (i,j), Prim’s algorithm maintains labels d(j) for each node j not yet added to the spanning tree:

d(j) = minimum cost of an arc (i,j) with i P

Prim’s algorithm also keeps track of which node i P has cij = d(j) by setting pred(j) := i.

algorithm PRIM;

begin

P := {1} ; T := N\{1}; F := ;

d(1) := 0 and pred(1) := ;

d(j) := c1j and pred(j) := 1 for all (1,j)  A ,

and d(j) :=  otherwise;

while P  N do

begin

{node selection, also called FINDMIN }

let i T be a node with d(i) = min{d(j): jT};

P := P{i}; T := T\{i}; add (i,pred(i)) to F;

{cost update}

for each (i,j)  A(i) do

if d(j) > cij then d(j) := cij and pred(j) := i;

end;

end

  • Where have we seen this algorithm before?

algorithm DIJKSTRA;

begin

P := {1} ; T := N\{1};

d(1) := 0 and pred(1) := ;

d(j) := c1j and pred(j) := 1 for all (1,j)  A,

and d(j) :=  otherwise;

while P N do

begin

{ node selection, also called FINDMIN }

select a node i  T with d(i) = min {d(j) : j T};

P := P{i}; T := T\{i};

{ distance update }

for each (i,j)  A(i) do

if d(j) > d(i)+cij then

d(j) := d(i)+cij and pred(j) := i;

end;

end

RUNNING TIME

Naïve Implementation:

Prim’s algorithm can be implemented using heaps.

Recall that the standard heap implementation has the following running times per operation:

FIND-MIN: O(1)

DECREASE-KEY:O(logn)

DELETE-MIN:O(logn)

INSERT:O(logn)

Heap Implementation:

Note: Prim’s algorithm can also be implemented using Fibonacci heaps in O(m+nlogn) time.

EXAMPLE

The set F of arcs is "grown" starting from node 1:

12345

d( ) / 0 / 35 / 40 /  / 

12345

d( ) / 0 / 35 / 25 / 10 / 

12345

d( ) / 0 / 35 / 20 / 10 / 30

12345

d( ) / 0 / 35 / 20 / 10 / 15

12345

d( ) / 0 / 35 / 20 / 10 / 15

SENSITIVITY ANALYSIS

Suppose that T* is a minimum cost spanning tree. For any arc (i,j) A, the cost interval of (i,j) is the range of values of cij for which T* continues to be a minimum cost spanning tree.

  • How can we find the cost interval of an arc (i,j) T*?
  • How can we find the cost interval of an arc (i,j) T*?

COMPREHENSIVE SENSITIVITY ANALYSIS

  • How much time does it take to find the cost intervals for every arc (i,j) T*?

max-cost arc in path from i to j

1 / 2 / 3 / 4 / 5
1
2
3
4
5

In the homework, you will show that all of these values can be computed in O(n2) time.

  • How much time does it take to find the cost intervals for every arc (i,j) T*?

SUMMARY

  1. The minimum cost spanning tree (MST) problem is an important problem in its own right.
  1. The MST problem is also an important sub-problem.
  1. The greedy algorithm works.
  1. Other very efficient algorithms.
  1. Sensitivity analysis can be performed efficiently.