flow networks Definition. A flow network is a directed graph G=(, E)with two distinguished vertices:a source s and a sink t. Each edge(u, v)E E has a nonnegative capacity c(u, v). If(u, v) E, then c(u, v)=0 Example: c 2001 by Charles E Leiserson

Recall from lecture 22 °Flow value:f=f(s,V) Cut: Any partition (S, T)of y such that s E S andt∈T Lemma. f=f(s, T) for any cut(S, T) Corollary. f(s, T) for any cut(S, T) Residual graph: The graph G=(v, ef) with strictly positive residual capacities c u, v) c(u,)-f(2y)>0

麻省理工学院：《算法导论》（英文版） Lecture 21 Prof charles e. leiserson

Shortest paths Single-source shortest paths nonnegative edge weights Dijkstra's algorithm: O(E+ vlg n General

Paths in graphs Consider a digraph g=(v, E)with edge-weight function w:E→>R. The weight of path p=v1→ →>…→> vi is defined to be (D)=∑(n,1)

Dynamic programming Design technique, like divide-and-conquer Example: Longest Common Subsequence (LCs) Given two sequences x[l.. m] and yll.n], find a longest subsequence common to them both a' not the

Fixed -universe successor problem Goal: maintain a dynamic subset s of size n of the universe 0=10, 1,.,u-1 of size u subject to these operations INSERT(X∈U\\S): Add x to s DELETE(X E S): Remove x from S

ynamic order statistics OS-SELECT(i, S): returns the i th smallest element in the dynamic set S. OS-RANK(, S): returns the rank ofx E S in the sorted order of s s elements IDEA: Use a red-black tree for the set S, but keep subtree sizes in the nodes

Binary-search-tree sort 7∈ b Create an empty Bst for i=i to n do trEe-INSert(,AiD) Perform an inorder tree walk of t Example:

Symbol-table problem Symbol table T holding n records