4. NETWORK ALGORITHMS
A network is a graph, often directed, with numbers assigned to each edge.
4.1 Shortest Paths
Find the shortest path between two given points, call them a and z in a directed network. The key idea is that to find the shortest path from a to z, one must first find the shortest paths from a to intermediate vertices.
To do this, Dijstra’s Algorithm solves the sequence of problems: How far can we get in 1 unit of distance? In 2 units? In 3 units? . . . . In m units. It builds a breadth-first spanning tree of shortest paths.
Example 1: In a failed marriage, find the shortest path from N (Niagara Falls) to R (Reno).
Let k(e) denote the length of edge e.
Dijstra’s Shortest Path Algorithm from a to z
1. Set distance counter m=1 and label a with (–,0).
2. Check each edge e =(p,q) from a labeled vertex p to an unlabeled vertex q. Suppose p’s second label is d(p). If d(p) + k(e) = m, label q with (p,m).
3. If z is not labeled yet, increment m by 1 and go to Step 2. Otherwise go to Step 4.
4. We have found a shortest path from a to z of length d(z), the second label of z. Such a path may be found by backtracking from z using the first label.
4.2. Minimum Spanning Trees.
For a given (undirected) network of n vertices, we seek a spanning tree of n-1 edges that minimizes the sum of the lengths of the edges. There are two ‘greedy’ algorithms that solve this problem.
Prim’s Algorithm
Repeat the following step until T has n – 1 edges: add to T the shortest edge between a vertex in T and a vertex not in T (initially pick any edge of shortest length).
Proof of Validity of Prim’s Algorithm
For simplicity, all edges have different lengths. Suppose the k-th edge ek =(a,b) chosen in Prim’s Alg is the first edge that is not in the true minimum spanning tree MSP (the tree T’ of first k-1 common edges are in red). The true MSP must have a path P of edges that connect T’ with vertex b. Let e* be the first edge of P. Since Prim’s Alg chose ek over e*, ek must be shorter. Then replacing e* by ek in the true MSP yields a shorter tree. Contradiction.
Kruskal’s Algorithm
Repeat the following step until our set of edges has n-1 edges (initially T is empty): add to T the shortest edge that does not form a circuit with edges already in T.
NETWORK FLOWS Sections IV.3,4
An a-z flow in a network N is an integer-valued function f(e) on the edges e satisfying, where a is the source and z is the sink:
a) 0 ≤ f(e) ≤ k(e) for each e; k(e) is the ‘capacity’ of e,
b) for x ≠ a or z,
c) f(e) = 0 if e In(a) or e Out(z)
Example 1: There are 3 power plants b,c,d with maximum supplies of 60, 40 and 40 megawatts, and 3 factories h,i,j with demands of 50, 40, 40 megawatts.
Is there a way to route electricity from the plants to meet the demands at all the factories.
A cut is the set of all edges from a vertex in P to a vertex in (i.e., not in P).
is called an a-z cut, if a P and z .
If we sum the conservation of flow equations (b) over all vertices in a set P (not containing a or z), condition b) generalizes to
Flow into P: 4 + 8 + 1 Flow out of P: 6 + 2 + 5
Theorem 1: For any a-z flow f(e) in a network N, the sum of the flows out of a equals the sum of the flows into z.
This sum is called the value |f| of the a-z flow f(e).
We define the capacity k of a cut to be the sum of the capacities of the edges in that cut.
In the earlier network, the capacity of the a-z cut that is represented by the dashed line is 5+3+5.
Theorem 2: For any a-z flow f and any a-z cut ,
Proof: Add a “super source” a’ not in P.
Corollary: |f| =k if and only if Our algorithm will
(i) for each e in , f(e) = k(e) ensure (i) and (ii)
(ii) for each e in (,P), f(e) = 0 are satisfied
We build flow in a network with flow paths from a to z. That is, we find a path P from a to z and send the same amount through every edge in P. To satisfy the capacity constraint in each edge, the value of this path flow cannot exceed the capacity of any edge in the P.
For example, the path L1 = a-b-d-z in the figure below can send up to 3 units, since edge (b,d) has a capacity of 3.
Slacks after first three flow paths (the slack s(e) = k(e) – f(e) tells how much more could be sent in an edge).
Now we switch the positions of d and e in this network, and repeat the routing of flow along the top, along the middle, and inbetween. We get:
The key is not to use paths but chains in which new flow can push against existing flow: send 2 units along a-c-e-b-d-z.
Corrected flow
Ford-Fulkerson Augmenting Flow Algorithm
For an edge e between labeled vertex p, with second label ∆(p), and unlabeled vertex q
If and s(e) = k(e)- f(e) >0
label q (p+, ∆(q)), where ∆(q) = min{s(e), ∆(p)}
b) If and f(e) > 0
label q (p-, ∆(q)), where ∆(q) = min {f(e), ∆(p)}
Theorem 3: For any given a-z flow f, a finite number of applications of the Augmenting Flow Algorithm yields a maximum a-z flow. Moreover, if P is the set of vertices labeled during the final (unsuccessful) application of the algorithm, then is a minimum a-z cut.
Example: Find maximum number of edge disjoint paths from a to z in this graph
Give every edge capacity of 1 (allow two-way flow) and find max flow from a to z to solve problem.
IV.3 Matching
A maximal matching is a matching of the largest size.
To find larger matching, use the Augmenting Flow Algorithm.
Resulting matching: c-g, b-g, b-j, e-j, e-k, plus old d-m, f-i
When we restate the max-flow=min cut theorem in the matching model, the min cut is a smallest set of edges out of a and into z that blocks all flow. These edges are identified with unique vertices. So we are looking for a minimum set of vertices that cover all matching edges.
Theorem: In a bipartite graph G = (X,Y,E), the size of a maximum matching equals the size of a minimum edge cover.
(Very hard to prove directly with graph theory.)
P = {a*,A, B, D, c, d}
Are the Bears mathematically eliminated from first place?
The real question is: If the Bears win all their remaining games—finishing with 23 wins– is there a set of outcomes of the games among the other teams such that no other team wins more than 23 games? For example, Lions can have at most 1 more win, etc. The following network flow models this situation. We want a flow that saturates all the edges into z (their capacities are the numbers of games to be played in each series).
4.5 The TRANSPORTATION PROBLEM
The cost of a solution using edges (1,1), (2,1), (2,2), and (3,2) is
(1,1) (2,1) (2,2) (3,2)
30x$4 + 30x$6 + 30x$6 + 20x$6 = $600 (ignore (1,3), (3,3) )
If we increase flow on (1,1), (2,2),(3,3) by 1 and decrease on (2,1), (3,2), (1,3) by 1, the solution changes by (4+6+0) – (6+6+0) = -2. To get an even cheaper solution, we should repeat this change until the flow is 0 in one of the decreasing edges—a change of 10 drives (1,3) to 0. This pattern happens in any circuit.
Theorem: An optimal (cheapest) solution will be a spanning tree.
Min Cost Algorithm
1. Find an initial spanning tree solution with the Northwest Corner rule.
60 50 20
2. Create selling prices for the commodity at warehouse i , call it ui, and at store j, call it vj that satisfy cij = vj – ui for the edges in the current solution. Arbitrarily start with u1 = 10.
When prices are determined by the condition that for edges in the current solution cij = vj – ui, then
Proof: Observe that
Summing over all i and j in this equation, we get the above result.
3. Look for an edge not in solution that would reduce the cost by adding that edge to the solution.
Increase flow in c12 to reduce the cost of the solution.
Remember that, besides edge (1,2), changes can only be made in edges that are part of the current solution (current spanning tree).
With both x11 and x22 going to 0, we lost the spanning tree (called a degenerate solution). Keep one 0-edge , say x22=0
Now we go back to steps 2 and 3 again.
New prices are
Warehouses: u1 = 10, u2 = 6, u3 = 6,
Stores: v1 = 12, v2 = 12, v3 = 6,
Check relative prices at non-tree edges.
No new edge will reduce the cost. So the current solution is optimal.
f (e) = f (e)
f(e)= f(e)
f (e) = f (e)
f(e)= f(e)