Unit8-sp

  • May 2020
  • PDF

This document was uploaded by user and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this DMCA report form. Report DMCA


Overview

Download & View Unit8-sp as PDF for free.

More details

  • Words: 5,827
  • Pages: 65
Unit 8: Graphs

․Course contents: ⎯ ⎯ ⎯ ⎯

Elementary graph algorithms Minimum spanning trees Shortest paths Maximum flow

․Reading: ⎯ ⎯

Unit 8

Chapters 22, 23, 24, 25 Chapter 26.1—26.3

Y.-W. Chang

1

Graphs

․A graph G = (V, E) consists of a set V of vertices (nodes) and a set E of directed or undirected edges. ⎯

For analysis, we use V for |V| and E for |E|.

․Any binary relation is a graph. ⎯

Unit 8

Network of roads and cities, circuit representation, etc.

Y.-W. Chang

2

Representations of Graphs: Adjacency List

․Adjacency list: An array Adj of |V | lists, one for each vertex in V. For each u ∈ V, Adj[u] pointers to all the vertices adjacent to u. ․Advantage: O(V+E) storage, good for sparse graph. ․Drawback: Need to traverse list to find an edge.

2

Unit 8

Y.-W. Chang

3

Representations of Graphs: Adjacency Matrix

․Adjacency matrix: A |V| r |V| matrix A = (aij) such that

․Advantage: O(1) time to find an edge. ․Drawback: O(V2) storage, more suitable for dense graph. ․How to save space if the graph is undirected?

Unit 8

Y.-W. Chang

4

Tradeoffs between Adjacency List and Matrix

Unit 8

Y.-W. Chang

5

Breadth-First Search (BFS) BFS(G,s) 1. for each vertex u ∈ V[G]-{s} 2. color[u] ← WHITE; 3. d[u] ← ∞; 4. π [u] ← NIL; 5. color[s] ← GRAY; 6. d[s] ← 0; 7. π[s] ← NIL; 8. Q ← {s}; 9. while Q ≠ ∅ 10. u ← head[Q]; 11. for each vertex v ∈ Adj[u] 12. if color[v] = WHITE 13. color[v] ← GRAY; 14. d[v] ← d[u]+1; 15. π [v] ← u; 16. Enqueue(Q,v); 17. Dequeue(Q); 18. color[u] ← BLACK. Unit 8

․ color[u]: white

(undiscovered) → gray (discovered) →black (explored: out edges are all discovered) ․ d[u]: distance from source s; π[u]: predecessor of u. ․ Use queue for gray vertices. ․ Time complexity: O(V+E) (adjacency list).

Y.-W. Chang

6

BFS Example 1

․ color[u]: white (undiscovered) → gray (discovered) → black (explored: out edges are all discovered) ․ Use queue Q for gray vertices. ․ Time complexity: O(V+E) (adjacency list). ⎯ Each vertex is enqueued and dequeued once: O(V) time. ⎯ Each edge is considered once: O(E) time. ․ Breadth-first tree: Gπ = (Vπ, Eπ), Vπ = {v ∈ V | π [v] ≠ NIL} ∪ {s}, Eπ = {(π[v], v) ∈ E | v ∈ Vπ - {s}}. Unit 8

Y.-W. Chang

7

Depth-First Search (DFS) DFS(G) 1. for each vertex u ∈ V[G] 2. color[u] ← WHITE; 3. π [u] ←NIL; 4. time ← 0; 5. for each vertex u ∈ V[G] 6. if color[u] = WHITE 7. DFS-Visit(u).

․ color[u]: white (undiscovered)

DFS-Visit(u) 1. color[u] ← GRAY; /* white vertex u has just been discovered. */ 2. d[u] ← time ← time + 1; 3. for each vertex v ∈ Adj[u] /* Explore edge (u,v). */ 4. if color[v] = WHITE 5. π [v] ← u; 6. DFS-Visit(v); 7. color[u] ← BLACK; /* Blacken u; it is finished. */ 8. f[u] ← time ← time +1. Unit 8

→ gray (discovered) → black (explored: out edges are all discovered) ․ d[u]: discovery time (gray); f[u]: finishing time (black); π[u]: predecessor. ․ Time complexity: O(V+E) (adjacency list).

Y.-W. Chang

8

DFS Example

․ color[u]: white → gray → black. ․ Depth-first forest: Gπ = (V, Eπ), Eπ = {(π[v], v) ∈ E | v ∈ V, π[v] ≠ NIL}. Unit 8

Y.-W. Chang

9

Parenthesis Property

․In any depth-first search of G, for u, v in G, exactly one of the following three conditions holds: ⎯ [d[u], f[u]] and [d[v], f[v]] are disjoint. ⎯ [d[u], f[u]] is contained entirely within [d[v], f[v]], and u is a descendant of v. ⎯ [d[v], f[v]] is contained entirely within [d[u], f[u]], and v is a descendant of u.

Unit 8

Y.-W. Chang

10

Edge Classification

․Directed graph ⎯ ⎯ ⎯ ⎯

Tree edge: (u, v) with white v. Back edge: (u, v) with gray v. Forward edge: (u, v) with black v, d[u] < d[v]. Cross edge: (u, v) with black v, d[u] > d[v].

․Undirected graph ⎯ ⎯

Unit 8

Tree edge Back edge

Y.-W. Chang

11

BFS Application: Lee’s Maze Router ․ Find a path from S to T by “wave propagation.” ․ Discuss mainly on single-layer routing. ․ Strength: Guarantee to find a minimum-length connection between 2 terminals if it exists. ․ Weakness: Time & space complexity for an M × N grid: O(MN) (huge!)

Filling Unit 8

Y.-W. Chang

12

BFS + DFS: Soukup’s Maze Router ․ Depth-first (line) search is first directed toward target T until an obstacle or T is reached. ․ Breadth-first (Lee-type) search is used to “bubble” around an obstacle if an obstacle is reached. ․ Time and space complexities: O(MN), but 10--50 times faster than Lee's algorithm. ․ Find a path between S and T, but may not be the shortest!

Unit 8

Y.-W. Chang

13

DFS Application: Hightower’s Maze Router

․A single escape point on each line segment. ․If a line parallels to the blocked cells, the escape point is placed just past the endpoint of the segment. ․Time and space complexities: O(L), where L is the # of line segments generated.

Unit 8

Y.-W. Chang

14

Topological Sort ․ A topological sort of a directed acyclic graph (DAG) G = (V, E) is a linear ordering of V s.t. (u, v) ∈ E ⇒ u appears before v.

Topological-Sort(G) 1. call DFS(G) to compute finishing times f[v] for each vertex v 2. as each vertex is finished, insert it onto the front of a linked list 3. return the linked list of vertices

․ Time complexity: O(V+E) (adjacency list).

Unit 8

Y.-W. Chang

15

Strongly Connected Component (SCC) ․ A strongly connected component (SCC) of a directed graph G=(V, E) is a maximal set of vertices U ⊆ V s.t.

.

Strongly-Connected-Components(G) 1. call DFS(G) to compute finishing times f[u] for each vertex u 2. compute GT 3. call DFS(GT), but in the main loop of DFS, consider the vertices in order of decreasing f[u] (as computed in line 1) 4. output the vertices of each tree in the depth-first forest of step 3 as a separate strongly connected component

․ Time complexity: O(V+E) (adjacency list).

Unit 8

Y.-W. Chang

16

Strongly Connected Component (SCC) Properties ․ If two vertices are in the same SCC, no path between them ever leaves the component. ․ In any DFS forest, all vertices in the same SCC are in the same tree. ․ Forefather φ(u): vertex w s.t. and f[w] is maximum. ․ The forefather φ(u) of any vertex u in a depth-first tree is an ancestor of u. ⎯ ⎯

Unit 8

φ(u) and u lie in the same SCC. Forefathers are roots of the depth-first trees.

Y.-W. Chang

17

How Does the SCC Algorithm Work? ․ u and v lie in the same SCC iff they have the same forefather. ⎯

The SCCs are sets of vertices with the same forefather.

․ DFS(G) finds vertices with directed paths from roots; DFS(GT) finds vertices with directed paths to roots (also with paths from roots). ․ In line 3, processing vertices in order of decreasing f[u], then no edge from any previous depth-first tree goes into the current processed tree. ⎯

Unit 8

“Peel” off the SCCs one by one in decreasing order of finishing times.

Y.-W. Chang

18

Minimum Spanning Tree (MST) ․ Given an undirected graph G = (V, E) with weights on the edges, a minimum spanning tree (MST) of G is a subset T ⊆ E such that ⎯ ⎯ ⎯

T is connected and has no cycles, T covers (spans) all vertices in V, and sum of the weights of all edges in T is minimum.

․ |T| = |V| - 1. ․ Applications: circuit interconnection (minimizing tree radius), communication network (minimizing tree diameter), etc.

Unit 8

Y.-W. Chang

19

Growing a Minimum Spanning Tree (MST) ․ Grows an MST by adding one safe edge at a time. Generic-MST(G,w) 1. A ← ∅ ; 2. while A does not form a spanning tree 3. find an edge (u,v) that is safe for A; 4. A ← A ∪ {(u,v)}; 5. return A.

․ A cut (S, V-S) of a graph G = (V, E) is a partition of V. ․ An edge (u, v) ∈ E crosses the cut (S, V-S) if one of its endpoints is in S and the other is in V-S. ․ A cut respects the set A of edges if no edges in A crosses the cut.

Unit 8

Y.-W. Chang

20

Greedy-Choice Property for MST

․An edge is a light edge crossing a cut if its weight is the minimum of any edge crossing the cut. ․A light edge crossing the cut (S, V-S) is safe for A. ⎯ ⎯ ⎯

G = (V, E). A: subset of E including in some minimum spanning tree for G. (S, V-S): any cut respecting A.

․If (u, v) is a light edge, w(T‘) = w(T) - w(x, y) + w(u, v) ≤ w(T).

X

Unit 8

Y.-W. Chang

21

Kruskal's MST Algorithm MST-Kruskal(G,w) 1. A ← ∅ ; 2. for each vertex v ∈ V[G] 3. Make-Set(v); 4. sort the edges of E[G] by nondecreasing weight w; 5. for each edge (u,v) ∈ E[G], in order by nondecreasing weight 6. if Find-Set(u) ≠ Find-Set(v) 7. A ← A ∪ {(u, v)}; 8. Union(u,v); 9. return A;

․ Add a safe edge at a time to the growing forest by finding an edge of least weight (from those connecting two trees in the forest). ․ Time complexity: O(E lgE + V) (= O(E lgV + V), why?) ⎯ Lines 2--3: O(V). ⎯ Line 4:O(E lgE). ⎯ Lines 5--8: O(E) operations on the disjoint-set forest, so O(E α(E, V)). Unit 8

Y.-W. Chang

22

Example: Kruskal's MST Algorithm

Unit 8

Y.-W. Chang

23

Prim's (Prim-Dijkstra's?) MST Algorithm MST-Prim(G,w,r) /* Q: priority queue for vertices not in the tree, based on key[]. */ /* key: min weight of any edge connecting to a vertex in the tree. */ 1. Q ← V[G]; 2. for each vertex u ∈ Q 3. key[u] ← ∞; 4. key[r] ← 0; 5. π[r] ← NIL; 6. while Q ≠ ∅ 7. u ← Extract-Min(Q); 8. for each vertex v ∈ Adj[u] 9. if v ∈ Q and w(u,v) < key[v] 10. π[v] ← u; 11. key[v] ← w(u,v)

․ Starts from a vertex and grows until the tree spans all the vertices. ⎯ ⎯

Unit 8

The edges in A always form a single tree. At each step, a safe, light edge connecting a vertex in A to a vertex in V - A is added to the tree. Y.-W. Chang

24

Example: Prim's MST Algorithm Key[a]=0 π[a]=NIL

Key[c]=8 π[c]=b

Key[b]=4 π[b]=a

Key[h]=8 π[h]=a

Key[d]=7 π[d]=c

Key[h]=8 π[h]=a

Key[i]=2 π[i]=c

Key[h]=8 π[h]=a

Key[d]=7 π[d]=c

Key[f]=4 π[f]=c

Key[h]=7 Key[g]=6 Key[f]=4 π[f]=c π[h]=i π[g]=i

Unit 8

Y.-W. Chang

25

Time Complexity of Prim's MST Algorithm MST-Prim(G,w, r) 1. Q ← V[G]; 2. for each vertex u ∈ Q 3. key[u] ← ∞; 4. key[r] ← 0; 5. π[r] ← NIL; 6. while Q ≠ ∅ 7. u ← Extract-Min(Q); 8. for each vertex v ∈ Adj[u] 9. if v ∈ Q and w(u,v) < key[v] 10. π[v] ← u; 11. key[v] ← w(u,v)

․ Q is implemented as a binary heap: O(E lg V). Lines 1--5: O(V). ⎯ Line 7: O(lg V) for Extract-Min, so O(VlgV) with the while loop. ⎯ Lines 8--11: O(E) operations, each takes O(lgV) time for DecreaseKey (maintaining the heap property after changing a node). ․ Q is implemented as a Fibonacci heap: O(E + VlgV). (Fastest to date!) ․ |E| = O(V) ⇒only O(E lg*V) time. (Fredman & Tarjan, 1987) ⎯

Unit 8

Y.-W. Chang

26

Complexity of Mergeable Heaps

․ Make-Heap(): creates and returns a new heap containing no elements. ․ Minimum(H): returns a pointer to the node with the minimum key. ․ Extract-Min(H): deletes the node with the minimum key. ․ Decrease-Key(H, x, k): assigns to node x the new key value k, which is ≤ its current key value. ․ Delete(H, x): deletes node x from heap H. Unit 8

Y.-W. Chang

27

Single-Source Shortest Paths (SSSP)

․The Single-Source Shortest Path (SSSP) Problem ⎯



Given: A directed graph G=(V, E) with edge weights, and a specific source node s. Goal: Find a minimum weight path (or cost) from s to every other node in V.

․Applications: weights can be distances, times, wiring cost, delay. etc. ․Special case: BFS finds shortest paths for the case when all edge weights are 1 (the same).

Unit 8

Y.-W. Chang

28

Negative Cycles in Shortest Paths ․ A weighted, directed graph G = (V, E) with the weight function w: E → R. ⎯ ⎯

Weight of path p = : w(p) = Shortest-path weight from u to v, δ(u, v):



k i =1

w(v i −1, v i ) .

․ Warning! negative-weight edges/cycles are a problem. ⎯ ⎯

Cycle <e, f, e> has weight -3 < 0 ⇒ δ(s, g) = - ∞. Vertices h, i, j not reachable from s ⇒ δ(s, h) = δ(s, i) = δ(s, j) = ∞.

․ Algorithms apply to the cases for negative-weight edges/cycles??

Unit 8

Y.-W. Chang

29

Optimal Substructure of a Shortest Path ․ Subpaths of shortest paths are shortest paths. ⎯

Let p = be a shortest path from vertex v1 to vertex vk, and let pij = be the subpath of p from vertex vi to vertex vj, 1 ≤ i ≤ j ≤ k. Then, pij is a shortest path from vi to vj.

․ Suppose that a shortest path p from a source s to a vertex v can be decomposed into

. Then, δ(s, v) = δ(s, u) + w(u, v).

․ For all edges (u, v) ∈ E, δ(s, v) ≤ δ(s, u) + w(u, v).

Unit 8

Y.-W. Chang

30

Relaxation Initialize-Single-Source(G, s) 1. for each vertex v ∈ V[G] 2. d[v] ← ∞; /* upper bound on the weight of a shortest path from s to v */ 3. π[v] ←NIL; /* predecessor of v */ 4. d[s] ← 0;

Relax(u, v, w) 1. if d[v] > d[u]+w(u, v) 2. d[v] ← d[u]+w(u, v); 3. π[v] ← u;

․ d[v] ≤ d[u] + w(u, v) after calling Relax(u, v, w). ․ d[v] ≥ δ(s, v) during the relaxation steps; once d[v] achieves its

lower bound δ(s, v), it never changes. ․ Let be a shortest path. If d[u] = δ(s, u) prior to the call Relax(u, v, w), then d[v] = δ(s, v) after the call.

Unit 8

Y.-W. Chang

31

Dijkstra's Shortest-Path Algorithm Dijkstra(G, w, s) 1. Initialize-Single-Source(G, s); 2. S ← ∅ ; 3. Q ← V[G]; 4. while Q ≠ ∅ 5. u ← Extract-Min(Q); 6. S ← S ∪ {u}; 7. for each vertex v ∈ Adj[u] 8. Relax(u, v, w);

․ Combines a greedy and a dynamic-programming schemes. ․ Works only when all edge weights are nonnegative. ․ Executes essentially the same as Prim's algorithm. ․ Naive analysis: O(V2) time by using adjacency lists.

Unit 8

Y.-W. Chang

32

Example: Dijkstra's Shortest-Path Algorithm d[u]=10 π[u]=s

d[u]=8 π[u]=x

d[v]=14 π[v]=x

d[s]=0 π[s]=NIL d[x]=5 π[x]=s

Unit 8

Y.-W. Chang

d[y]=7 π[y]=x

33

Runtime Analysis of Dijkstra's Algorithm Dijkstra(G, w, s) 1. Initialize-Single-Source(G, s); 2. S ← ∅ ; 3. Q ← V[G]; 4. while Q ≠ ∅ 5. u ← Extract-Min(Q); 6. S ← S ∪ {u}; 7. for each vertex v ∈ Adj[u] 8. Relax(u, v, w);

․ Q is implemented as a linear array: O(V2). ⎯ ⎯

Line 5: O(V) for Extract-Min, so O(V2) with the while loop. Lines 7--8: O(E) operations, each takes O(1) time.

․ Q is implemented as a binary heap: O(E lg V). ⎯ ⎯

Line 5: O(lg V) for Extract-Min, so O(V lg V) with the while loop. Lines 7--8: O(E) operations, each takes O(lg V) time for DecreaseKey (maintaining the heap property after changing a node).

․ Q is implemented as a Fibonacci heap: O(E + V lg V). Unit 8

Y.-W. Chang

34

The Bellman-Ford Algorithm for SSSP Bellman-Ford(G,w, s) 1. Initialize-Single-Source(G, s); 2. for i ← 1 to |V[G]|-1 3. for each edge (u, v) ∈ E[G] 4. Relax(u, v, w); 5. for each edge (u, v) ∈ E[G] 6. if d[v] > d[u] + w(u, v) 7. return FALSE; 8. return TRUE

․ Solves the case where edge weights can be negative. ․ Returns FALSE if there exists a negative-weight cycle reachable from the source; TRUE otherwise. ․ Time complexity: O(VE).

Unit 8

Y.-W. Chang

35

Example: The Bellman-Ford Algorithm

Unit 8

Y.-W. Chang

36

SSSPs in Directed Acyclic Graphs (DAGs) DAG-Shortest-Paths(G, w, s) 1. topologically sort the vertices of G; 2. Initialize-Single-Source(G, s); 3. for each vertex u taken in topologically sorted order 4. for each vertex v ∈ Adj[u] 5. Relax(u, v, w);

․ Time complexity: O(V+E) (adjacency-list representation).

Unit 8

Y.-W. Chang

37

Linear Programming ․ Linear programming (LP): Mathematical program in which the objective function is linear in the unknowns and the constraints consist of linear equalities (inequalities). ․ Standard form: min/max c1 x1 + c2 x2 + … + cn xn subject to a11x1 + a12x2 + … + a1n xn ≤ b1 … am1x1 + am2x2 + … + amnxn ≤ bm and x1 ≥ 0, x2 ≥ 0, …, xn ≥ 0.

․ Compact vector form: min/max cTx subject to Ax ≤ b and x ≥ 0, where x is an n-dimensional column vector, cT is an n-dimensional row vector, A is an m × n matrix, and b is an m-dimensional column vector. x ≥ 0 means that each component of x is nonnegative. Unit 8

Y.-W. Chang

38

Difference Constraints ․ System of difference constraints: Each row of the linear-programming matrix A contains exactly one 1, one -1, and 0's for all other entries. ⎯ Form: xj - xi ≤ bk, 1 ≤ i, j ≤n, 1 ≤ k ≤m. ․ Example:

․ Equivalent to finding the unknowns xi, i = 1, 2, …, 5 s.t. the following difference constraints are satisfied:

Unit 8

Y.-W. Chang

39

Constraint Graph ․ x = (x1, x2, …, xn) is a solution to Ax ≤ b of difference constraints ⇒ so is x + d = (x1 + d, x2 + d, …, xn+ d). ․ Constraint graph: Weighted, directed graph G=(V, E). ⎯ V = { v0, v1, …, vn} ⎯ E = {(vi, vj): xj - xi ≤ bk} ∪ {(v0, v1), (v0, v2),…, (v0, vn)} ⎯ w(vi, vj) = bk if xj - xi ≤ bk is a difference constraint. ․ If G contains no negative-weight cycle, then x = (δ(v0, v1), δ(v0, v2), …, δ(v0, vn)) is a feasible solution; no feasible solution, otherwise. ․ Example: x = (-5, -3, 0, -1, -4) and x' =(d-5, d-3, d, d-1, d-4) are feasible solutions. δ(v0, vj) ≤ δ(v0, vi) + w(vi, vj)

xj

Unit 8

xi

bk

Y.-W. Chang

40

All-Pairs Shortest Paths (APSP) ․ The All-Pairs Shortest Path (APSP) Problem Given: A directed graph G = (V, E) with edge weights ⎯ Goal: Find a minimum weight path (or cost) between every pair of vertices in V. ․ Method 1: Extends the SSSP algorithms. ⎯ No negative-weight edges: Run Dijkstra's algorithm |V| times, once with each v ∈ V as the source. 2 „ Adjacency list + Fibonacci heap: O(V lg V + VE) time. ⎯ With negative-weight edges: Run the Bellman-Ford algorithm |V| times, once with each v ∈ V as the source. 2 „ Adjacency list: O(V E) time. ․ Method 2: Applies the Floyd-Warshall algorithm (negative-weight edges allowed). 3 ⎯ Adjacency matrix: O(V ) time. ․ Method 3: Applies Johnson's algorithm for sparse graphs (negative-weight edges allowed). 2 ⎯ Adjacency list: O(V lg V + VE) time. ⎯

Unit 8

Y.-W. Chang

41

Overview of Floyd-Warshall’s APSP Algorithm ․ Applies dynamic programming. Characterize the structure of an optimal solution? 2. Recursively define the value of an optimal solution? 3. Compute the value of an optimal solution in a bottom-up fashion? 4. Construct an optimal solution from computed information? Uses adjacency matrix A for G = (V, E) : 1.



․ Goal: Compute |V| r |V| matrix D where D[i, j] = dij is the weight of ․ ․ Unit 8

a shortest i-to-j path. Allows negative-weight edges. Runs in O(V3) time.

Y.-W. Chang

42

Shortest-Path Structure ․ An intermediate vertex of a simple path is any vertex in {v2, v3, …, vl-1}.

․ Let

be the weight of a shortest path from vertex i to vertex j

with all intermediate vertices in {1, 2, …, k}. ⎯

The path does not use vertex k:



The path uses vertex k:

. .

․ Def: Dk[i, j] =

is the weight of a shortest i-to-j path with intermediate vertices in {1, 2, …, k}.

Unit 8

Y.-W. Chang

43

The Floyd-Warshall Algorithm for APSP Floyd-Warshall(W) 1. n ← rows[W]; /* W = A */ 2. D(0) ← W; 3. for k ← 1 to n 4. for i ← 1 to n 5. for j ← 1 to n 6. 7. return D(n);

․D(k)[i, j] =

: weight of a shortest i-to-j path with intermediate vertices in {1, 2, …, k}. ⎯



D(0) = A: original adjacency matrix (paths are single edges). D(n) = ( ): the final answer ( = δ(i, j)).

․Time complexity: O(V 3). ․Question: How to detect negative-weight cycles? Unit 8

Y.-W. Chang

44

Constructing a Shortest Path ․ Predecessor matrix Π = (πij): πij is ⎯ ⎯

NIL if either i=j or there is no path from i to j, or Some predecessor of j on a shortest path from i

․ Compute Π(0), Π (1), …, Π (n), where

is defined to be the

predecessor of vertex j on a shortest path from i with all intermediate vertices in {1, 2, …, k}.

Print-All-Pairs-Shortest-Path(Π, i, j) 1. if i=j 2. print i; 3. else if πij = NIL 4. print “no path from i to j exists”; 5. else Print-All-Pairs-Shortest-Path(Π, i, πij); 6. print j; Unit 8

Y.-W. Chang

45

Example: The Floyd-Warshall Algorithm

Unit 8

Y.-W. Chang

46

Transitive Closure of a Directed Graph ․ The Transitive Closure Problem: ⎯ ⎯

Input: a directed graph G = (V, E) Output: a |V| r |V| matrix T s.t. T[i, j] = 1 iff there is a path from i to j in G.

․ Method 1: Run the Floyd-Warshall algorithm on unit-weight

graphs. If there is a path from i to j (T[i, j] = 1), then dij < n; dij = ∞ otherwise. ⎯ ⎯

Runs in O(V3) time and uses O(V2) space. Needs to compute lengths of shortest paths.

․ Method 2: Define t

(k )

= 1 if there exists a path in G from i to j with all intermediate vertices in {1, 2, …, k}; 0 otherwise.

․ For k ≥ 1, t ⎯

Unit 8

(k ) ij

( k −1)

= t ij

ij

( k −1)

∨ (t ik

( k −1)

∧ t kj )

.

Runs in O(V3) time and uses O(V2) space, but only single-bit Boolean values are involved ⇒ faster!

Y.-W. Chang

47

Transitive-Closure Algorithm Transitive-Closure(G)

1. n ← |V[G]|; 2. for i ← 1 to n 3. for j ← 1 to n 4.

if i = j or (i, j) ∈ E[G]

5. ←1 6. else ←0 7. for k ← 1 to n 8. for i ← 1 to n 9. for j ← 1 to n 10. 11. return T(n).

Unit 8

Y.-W. Chang

48

Johnson's Algorithm for Sparse Graphs ․ Idea: All edge weights are nonnegative ⇒ Dijkstra's algorithm is



Unit 8

applicable (+Fibonacci-heap priority queue: O(V2 lg V + VE)). ⎯ Reweighting: If there exists some edge weight w < 0, reweight w to ≥ 0. ⎯ must satisfy two properties: 1. ∀u, v ∈ V, shortest path from u to v w.r.t. w ⇒ shortest path from u to v w.r.t. . 2. ∀ e ∈ E, (e) ≥ 0. Preserving shortest paths by reweighting: Given directed G = (V, E) with weight function w: E → R , let h: V → R . For each edge (u, v) ∈ E, define (u, v) = w(u, v) + h(u) - h(v). Let p = . Then 1. w(p) = δ(v0, vk) iff (p) = (v0, vk). 2. G has a negative cycle w.r.t w iff has a negative cycle w.r.t .

Y.-W. Chang

49

Preserving Shortest Paths by Reweighting

1. Show that w(p) = δ (v0, vk) ⇒ ,



(

(p') <

(p) =

(v0, vk). Suppose ∃ p'=

(p).

w(p') < w(p), contradiction! (p) = (v0, vk) ⇒ w(p) = δ(v0, vk): similar!)

2. Show that G has a negative cycle w.r.t w iff Unit 8

cycle w.r.t - h(v0) = w(c).

has a negative . Cycle c = ⇒ (c) = w(c) + h(v0) Y.-W. Chang

50

Producing Nonnegative Weights by Reweighting 1. Construct a new graph G' = (V', E'), where

2. 3. 4.

Unit 8

V' = V ∪ {s} E' = E ∪ {(s, v): v ∈ V} w(s, v) = 0, ∀v ∈ V G has no negative cycle ⇔ G' has no negative cycle. If G and G' have no negative cycles, define h(v) = δ(s, v), ∀v ∈ V'. Define the new weight for : (u, v) = w(u, v) + h(u) - h(v) ≥ 0 (since δ(s, v) ≤ δ(s, u) + w(u, v)).

Y.-W. Chang

51

Johnson's Algorithm for APSP Johnson(G) 1. compute G', where V[G']=V[G] ∪ {s} and E[G']=E[G] ∪{(s,v):v ∈ V[G]}; 2. if Bellman-Ford(G', w, s) = FALSE 3. print “the input graph contains a negative-weight cycle”; 4. else for each vertex v ∈ V[G'] 5. set h(v) to the value of δ(s,v) computed by the Bellman-Ford algorithm; 6. for each edge (u,v) ∈ E[G'] 7. (u,v) ← w(u, v) + h(u) - h(v); 8. for each vertex u ∈ V[G] 9. run Dijkstra(G, , u) to compute (u,v) for all v ∈ V[G]; 10. for each vertex v ∈ V[G] 11. duv ← (u, v) + h(v) - h(u); 12. return D;

․ Steps: Compute the new graph ⇒ Bellman-Ford ⇒ Reweighting ⇒ Dijkstra's (+ Fibonacci heap) ⇒ Recompute the weights. ․ Time complexity: O(V) + O(VE) + O(E) + O(V2 lg V + VE) + O(V2) = O(V2 lg V + VE). Unit 8

Y.-W. Chang

52

Example: Johnson's Algorithm for APSP h(v) h(u)

1 = 2 + (-1) - 0

Unit 8

Y.-W. Chang

53

Maximum Flow ․ Flow network: directed G=(V, E) ⎯ ⎯

capacity c(u, v) : c(u, v) > 0, ∀(u, v) ∈ E; c(u, v) = 0, ∀(u, v) ∉ E. Exactly one node with no incoming (outgoing) edges, called the source s (sink t).

․ Flow f: V r V → R that satisfies ⎯ ⎯ ⎯

Capacity constraint: f(u, v) ≤ c(u, v), ∀u, v ∈ V. Skew symmetry: f(u, v) = -f(v, u). Flow conservation: ∑v ∈ Vf(u, v) = 0, ∀u ∈ V - {s, t}.

․ Value of a flow f: |f| = ∑v ∈ V f(s, v) = ∑v ∈ V f(v, t), where f(u, v) is the net flow from u to v. ․ The maximum flow problem: Given a flow network G with source s and sink t, find a flow of maximum value from s to t.

Unit 8

Y.-W. Chang

54

Network with Multiple Sources and Sinks ․ Reduce a multiple-source, multiple-sink maximum-flow problem to a problem with a single source and a single sink. ⎯





Unit 8

Given a flow network with sources S = {s1, s2, …, sm} and sinks T = {t1,

t2, …, tn}, introduce a supersource s and edges (s, si), i = 1, 2, …, m, with capacity c(s, si) = ∞ and a supersink t and edges (ti, t), i = 1, 2, …, n, with capacity c(ti, t) = ∞. Any flow in a multiple-source, multiple-sink flow network corresponds to a flow of identical value in a single-source, single-sink flow network, and vice versa. Reduction cost?

Y.-W. Chang

55

Working with Flows

․If X, Y ⊆ V, f(X, Y) = ∑x ∈ X ∑y ∈ Yf(x, y). ․G= (V, E): flow network, f: flow in G ⎯ ⎯ ⎯

∀ X ⊆ V, f(X, X) = 0. ∀ X, Y ⊆ V, f(X, Y) = - f(Y, X). ∀ X, Y, Z ⊆ V with X ∩ Y = ∅ , f(X ∪Y, Z) = f(X, Z) + f(Y, Z) and f(Z, X ∪Y) = f(Z, X) + f(Z, Y).

․Value of flow = net flow into the sink: |f| = f(V, t). |f| = f (s, V) /* by definition */ = f (V, V) - f (V - s, V) /* V - s ≡ V - {s} */ = f (V, V - s) = f (V, t) + f(V, V - s - t) = f (V, t).

․Cancellating flow going in opposite direction:

Unit 8

Y.-W. Chang

56

Basic Ford-Fulkerson Method Ford-Fulkerson-Method(G, s, t) 1. Initialize flow f to 0; 2. while there exists an augmenting path p 3. Augment flow f along p; 4. return f;

․ Ford & Fulkerson, 1956 ․ Augmenting path: A path from s to t along which we can push more flow. ․ Need to construct a residual network to find an augmenting path.

Unit 8

Y.-W. Chang

57

Residual Network ․ Construct a residual network to find an augmenting path. ․ Residual capacity of edge (u, v), cf(u, v): Amount of additional net flow that can be pushed from u to v before exceeding c(u, v), cf (u, v) = c(u, v) - f(u, v). ․ Gf = (V, Ef): residual network of G = (V, E) induced by f, where Ef = {(u, v) ∈ V r V: cf (u, v) > 0}. ․ The residual network contains residual edges that can admit a positive net flow (|Ef| ≤ 2|E|). ․ Let f and f' be flows in G and Gf, respectively. The flow sum f + f ': V r V → R : (f + f ')(u, v) = f(u, v) + f'(u, v) is a flow in G with value |f + f '| = |f| + |f '|.

Unit 8

Y.-W. Chang

58

Augmenting Path ․ An augmenting path p is a simple path from s to t in the residual network Gf. ⎯



(u, v) ∈ E on p in the forward direction (a forward edge), f(u, v) < c(u, v). (u, v) ∈ E on p in the reverse direction (a backward edge), f(u, v) > 0.

․ Residual capacity of p, cf (p): Maximum amount of net flow that can be pushed along the augmenting path p, i.e., cf (p) = min{cf (u, v) : (u, v) is in p}. ․ Let p be an augmenting path in Gf. Define fp: V r V → R by

Then, fp is a flow in Gf with value |fp| = cf (p) > 0.

Unit 8

Y.-W. Chang

59

Cuts of Flow Networks

․ A cut (S, T) of flow network G = (V, E) is a partition of V into S and T = V - S such that s ∈ S and t ∈ T. ⎯



Capacity of a cut: c(S, T) =∑u ∈ S, v ∈ T c(u, v). (Count only forward edges!) f(S, T) = |f| ≤ c(S, T), where f(S, T) is net flow across the cut (S, T).

․ Max-flow min-cut theorem: The following conditions are equivalent 1. 2. 3.

Unit 8

f is a max-flow. Gf contains no augmenting path. |f| = c(S, T) for some cut (S, T).

Y.-W. Chang

60

Ford-Fulkerson Algorithm Ford-Fulkerson(G, s, t) 1. for each edge (u, v) ∈ E[G] 2. f[u, v] ← 0; 3. f[v, u] ← 0; 4. while there exists a path p from s to t in the residual network Gf 5. cf (p) ←min {cf (u, v): (u, v) is in p}; 6. for each edge (u, v) in p 7. f[u, v] ← f[u, v] + cf (p); 8. f[v, u] ← -f[u, v];

․ Time complexity (assume integral capacities): O(E |f *|), where f * is the maximum flow. ⎯ ⎯ ⎯

Unit 8

Each run augments at least flow value 1 ⇒ at most |f *| runs. Each run takes O(E) time (using BFS or DFS). Polynomial-time algorithm?

Y.-W. Chang

61

Example: Ford-Fulkerson Algorithm

Unit 8

Y.-W. Chang

62

Edmonds-Karp Algorithm ․ The Ford-Fulkerson algorithm may be bad when |f *| is very large. ⎯

2M iterations in the worst case v.s. 2 iterations.

․ Edmonds-Karp Algorithm (1969): Find an augmenting path by shortest path (minimum # of edges on the path), i.e., use breadthfirst search (BFS). ⎯



⎯ ⎯

Using the Edmonds-Karp algorithm, the shortest-path distance δf (s, v) in the residual network Gf increases monotonically with each flow augmentation. The # of flow augmentations performed by the Edmonds-Karp algorithm is at most O(VE). Each flow augmentation can be found in O(E) time by BFS. Total running time of the Edmonds-Karp algorithm is O(VE2).

․ Goldberg & Tarjan (1985): O(EV lg(V2/E)); Ahuja, Orlin, Tarjan (1989): O( Unit 8

) , U = max. edge capacity. Y.-W. Chang

63

Maximum Cardinality Matching ․ Given an undirected G=(V, E), M ⊆ E is a matching iff at most one edge of M is incident on v, ∀ v ∈ V. ⎯

v ∈ V is matched if some edge in M is incident on v; otherwise, v is unmatched.

․ M is a maximum matching iff |M| ≥ |M'| ∀ matching M'.

Maximal matching

Maximal matching

Maximum matching

Maximum matching

Unit 8

Y.-W. Chang

64

Application: Maximum Cardinality Bipartite Matching ․ Given a bipartite graph G = (V, E), V = L ∪ R, construct a unitcapacity flow network G' = (V', E'): V' = V ∪ {s, t} E '= {(s, u): u ∈ L} ∪{(u, v): u ∈ L, v ∈ R, (u, v) ∈ E} ∪{(v, t): v ∈ R}. ․ The cardinality of a maximum matching in G = the value of a maximum flow in G' (i.e., |M| = |f|). ․ Time complexity: O(VE) by the Ford-Fulkerson algorithm. ⎯

Unit 8

Value of maximum flow ≤ min(L, R) = O(V).

Y.-W. Chang

65