图G=( V. E ); V:定点集,E:边集

表示方法

邻接表

有向图:邻接表的长度之和为|E| 无向图:邻接表的长度之和为2|E| 存储空间:O( E + V )

    array GraphVertex[|V|] ;       //顶点数组

    struct Edge                    //边链表
        int VerID ;
        struct VertexLink *next ;

邻接矩阵

存储空间:O( V^2 ), nij = 1; (i,j)属于E nij = 0; (i,j)不属于E 对于无权值图,可用二进制位图表示

    array Graph[|V|][|V|] ;

图的操作

广度优先搜索

首先发现和s距离为k的所有顶点,然后才发现和s距离k+1的其他顶点 将每个顶点都着色为白,灰,黑 白:未被访问 其他:已被访问

    struct _vertex
        int v ;                 //顶点编号
        struct _vertex *pi ;    //父节点
        struct _vertex *next ;  //邻接表中指向下一条边
        COLOR   color ;         //着色
        int d ;                 //顶点S到v的距离
    vertex ;                    //在顶点集中不使用next
                                //在边集中使用v和next
    /*-------------*/
    struct _graph
        vertex *V ;             //顶点集
        vertex *adj ;             //边集
    graph ;
    BFS( G, s )                 //以s为源点,进行广度优先搜索
        for each v in V[G]-s
            pi[v] = nil ;
            color[v] = white ;
            d[v] = MAX_VALUE ;  //如果s到v无边,则 d[v] = MAX_VALUE

        pi[s] = nil ;
        color[s] = gray ;
        d[s] = 0 ;
        Q = InitialQueue( ) ;   //先进先出队列
        EnQueue( Q, s ) ;

        while !EmptyQueue( Q ) 
            u = DeQueue( Q ) ;

            for each v in adj[u]          
                if color[v] == white        
                    pi[v] = u ;
                    d[v] = d[u] + 1 ;
                    color[v] = gray ;   //相当于visit[v]
                    EnQueue( Q, v ) ;

            color[u] = black ;
    //T(n) = O( V + E )

设 G = ( V, E ) 是一个有向或无向图, s in V 为G的任意一个顶点,则对任意(u, v) in E, 有 M(s,v) <= M(s, u) + 1 (其中M为最短路径符号)

广度优先树

在BFS的同时,也建立了一棵广度优先树,且由 pi 域表示. 对于图 G = ( V, E ) 及给定的源顶点s, 可以更为形式的定义其前趋子图 Gpi = ( Vpi, Epi ), 其中 Vpi = { v in V : pi[v] != nil } and { s }, 且 Epi = { ( pi[v], v ) : v in ( Vpi - { s } ) }

    PrintPath( G, s, v )   //此过程输出从s到v的最短路径上的所有顶点
        if pi[v] == s      //假设已经运行了BFS来计算最短路径
            print s ;
        else if pi[v] == nil ;
            print "no way to s" ;
        else 
            PrintPath( G, s, pi[v] ) ;
            print v ; 

深度优先搜索

没有源点 对于新发现的顶点,如果它还有以此为起点而为探测到的边,就沿此边继续探测下去 形成深度优先森林 数据机构中多了: 1.d[v],第一个时间戳,第一次被发现时; 2.f[v],第二个时间戳,结束探查v的邻接表时

    DFS( G )
        for each u in V[G]
            pi[u] = nil ;
            color[u] = white ;

        for each u in V[G]
            if color[u] == white
                DFSVisit( u ) ;

    /*-------------*/
    DFSVisit( u )                //递归可以很方便的加上时间戳
        time++ ;                 //全局变量
        d[u] = time ;
        color[u] = gray ;

        for each v in adj[u]
            if color[v] == white
                pi[v] = u ;
                DFSVisit( v )
        
        time++ ;
        f[u] = time ;
        color[u] = black ;

在对一个(有向或无向)图 G = ( V, E ) 的任何深度优先搜索中,对于图中任意两个顶点 u 和 v , 下述两个条件仅有一个成立:

  1. 区间 [ d[u], f[u] ] 和区间 [ d[v], f[v] ] 是完全不相交的,且在深度优先森林中 u 或 v 都不是对方的后继
  2. 区间 [ d[u], f[u] ] 完全包含于 [ d[v], f[v] ] ,且在深度优先树中, u 是 v 的后裔
边的分类
  1. 树边:顶点v在探寻边(u, v)时,被首次发现
  2. 反向边:连接顶点u到它的某一祖先v的边
  3. 正向边:连接顶点u到它的某一后裔v的非树边
  4. 交叉边:其中一个顶点不是另一个顶点的祖先或后裔,但两个顶点有边相连,且在不同的深度优先树之间

根据到达顶点的颜色进行分类: a.白色:树边 b.灰色:反向边 c.黑色:正向边或回边 注:无向图只有树边和反向边

拓扑排序

  1. 对图G进行深度优先搜索
  2. 以顶点v的搜索完成时间f[v]降序排列

当且仅当对G进行深度优先搜索时,没有得到反向边,有向图G是无回路的

强连通分支

定义: a. 有向图G = ( V, E ) b. C 包含于 V, C 是一个顶点集, 且 |c| 最大 c. u in C, v in C, 有 u~>v 和 v~>u, 即v和u相互可达

在强连通分支算法中要用到图的转置 定义有向图 G = ( V, E ) 的转置图为 Gt = ( V, Et ), 其中 Et = { (u, v) : (v, u) in E }, 即:Et是G中的边改变方向所租成的

    StronglyConnectComponents( G )
        DFS( G ) ;
        DFS( Gt ) with topological order ;
        OutPut the forest computed by DFS( Gt ) ;

证明:定义 d(U) = min( d[u], u in V ), f(U) = max( f[u], u in V ), 其中U属于V

  1. 设C和C1为有向图 G = ( V, E ) 中两个不同的强连通分支.假设( u, v ) in E, 其中u in C, v in C1, 则f(C) > f(C1)
  2. 设C和C1为有向图 G = ( V, E ) 中两个不同的强连通分支.假设( u, v ) in Et, 其中u in C, v in C1, 则f(C) < f(C1)

这里的f[u]都是由 DFS( G ) 计算出来的. 1 和 2 其实是等价的

我们来看一看执行DFS(Gt)的情况: 设C和C1是两个不同的连通分量,且f(C) > f(C1). 设x是C中的一个顶点,且f[x] = f(C),即DFS(Gt)是从x开始. 假设存在一条边(u, v) in Et 连通C 和 C1,且u in C, v in C1, 则f(C) < f(C1),与f(C) > f(C1)矛盾 所以,在Et上,不存在C 到 C1的边,且从x开始的搜索不会访问任何其他强连通分支中的顶点

最小生成树

最小生成树的形成: 无向连通图G = ( V, E ) – 权值w( u, v) = { (u, v) in E : w( u, v ) 是一个实函数 } – 无回路子集T属于E, T = { 连接所有顶点 且 w(T) 最小 }

    GeneriMST( G, w )
        A = NULL ;              //边集

        while A does not FORM a spanning tree
            find a edge (u, v) that is safe for A
            A = A U (u, v) ;    //循环不变式:A是某个最小生成树边的子集
                                //           找出一条边(u,v),使其加入集合A,仍不
        return A ;              //           违反A是某个最小生成树的子集
                                //           即(u,v)是安全的
概念
  1. 割:对无向图 G = ( V, E ) 的一个割( S, V-S )是对V的一个划分,当一条边(u, v) in E, 且u in S, v in V-S, 则( u, v )通过割( S, V-S )
  2. 边集的妨害:边集A 属于 E 中,没有边通过某一割,则称该割不妨害A
  3. 轻边:一条边的权值是通过某一割的所有边的最小值

设图G = ( V, E )及加权函数w,设A是E的一个子集,且包含于G的某个最小生成树中.设割( S, V-S )是G的任意一个不妨害A的割,且边( u, v )是通过( S, V-S )的轻边,则边(u, v)对集合A来说是安全的

kruskal算法

集合A是一个森林,加入集合A中的安全边是连接这些森林的最小权边

    MSTkruskal( G, w )                  //w是加权函数,T(n) = O(ElgV)
        A = NULL ;

        for each u in V[G]
            MakeSet( u ) ;              //使用不相交集合ADT

        sort edge (u, v) in E[G] with increasing order by w(u, v) ;

        for each sorted edge (u, v) in E[G]
            if FindSet( u ) != FindSet( v )  //不相交集合ADT
                A = A U (u, v) ;
                UnionSet( u, v ) ;           //不相交集合ADT

prime算法

集合A仅形成单棵树(从任意顶点r开始),添加到集合A的安全边总是连接树与一个不在树中的顶点的最小权边.

    MSTprime( G, w, r )             //以r为树根生最小生成树
        for each u in V[G]
            key[u] = MAX_VALUE;     //u到pi[u]的距离
            pi[u] = nil ;           //pi[u]为u的父节点
        key[r] = 0 ;
        Q = V[G] ;                  //优先级队列,以key[u]为关键字

        while Q != NULL
            u = ExtractMin( Q ) ;
            for each v in adj[u]    //邻接表中节点连通表
                if v in Q           //可用位图在常数时间内确认
                    if key[v] > w( u, v )
                        key[v] = w( u, v ) ; //隐含DecreasingKey的操作
                        pi[v] = u ;

    //T(n) = O( ElgV)
    /*
    while循环每次迭代之前,有:
    a. A = { (v, pi[v]) : v in V - {r} - Q }
    b. 已经被放入最小生成树中的节点都是 V-Q 中的节点
    c. v in Q, key[v] != MAX_VALUE ==> pi[v] != nil,如其是一条轻边,则v是最小生成树中的节点
    */

单源最短路径

概述
  1. 已知图G=( V, E ),我们希望找出以某个给定源顶点s in V到每个顶点v in V的最短路径
  2. 带权有向图G=( V, E),加权函数w : E -> R
  3. 从u到v的最短路径为:M(u, v),min( w(p) : u ~> v ),有路径; MAX_VALUE,无路径.其中w(p)为 u ~> v 的路径权值之和, P = ( v0, v1, … ,vk ) 是路径
分析
最优子结构

设 P = ( v0, v1, … ,vk ) 是 v0 到 vk的最短路径,则 Pi in P 也是最短路径

表示
  1. pi[v]用于记录v的父节点
  2. 前趋子图Gpi = ( Vpi, Epi ) : Vpi = { v in V : pi[v] != nil }; Epi = { ( pi[v], v ) in E, v in Vpi - {s} }. 在算法结束时,Gpi就是最短路径树
  3. 松弛技术: 对每个顶点v in V设置一个属性d[v],用来表示从源点s到v的最短路径的上界,且 d[v] <= d[u] + w( u, v )
    InitialSingleSource( G, s )
        for each u in V[G]
            d[u] = MAX_VALUE ;
            pi[u] = nil ;
        d[s] = 0 ;

    /*----------*/
    Relax( u, v, w )        //w为加权函数
        if d[v] > d[u] + w( u, v )
            d[v] = d[u] + w( u, v )
            pi[v] = u ;
性质
  1. 三角不变式:对任意( u, v ) in E, 有M( s, v ) <= M( s, u ) + w( u, v )
  2. 上界性质:对任意顶点v in V, 有 d[v] >= M( s, v ),且当d[v] = M( s, v )时,d[v]不再改变
  3. 无路径性质:如从s到v不存在路径,则d[v] = M( s, v ) = MAX_VALUE
  4. 路劲松弛性质:如果P=( v0, v1, … , vk )是从s=v0到vk的最短路径,而且P的边按照( v0, v1 ), ( v1, v2 ), … , ( vk-1, vk )的顺序进行松弛,那么d[vk] = M( s, vk ),这个性质的保持并不受其他松弛操作的影响,即使它们与P的边上的松弛操作混合在一起也是一样
实现
bellmanFord算法

该算法能在一般情况下(存在负权边)解决单元最短路径问题.返回一个布尔值:true,产生最短路径及权值;false,有负权回路

    bellmanFord( G, s, w )          //s是源点,w是加权函数, T(n) = O(VE)
        InitialSingleSource( G, s ) ;
        for i = 1 to |V|
            for each edge (u, v) in E[G]
                Relax( u, v, w ) ;

        for each edge (u, v) in E[G]
            if d[v] > d[u] + w(u, v)
                return false ;

        return true ;

    /*
    设C = ( v0, v1, ... , vk )为一条负权回路,其中vk = v0,则SUM( w( vi-1, vi ) ) < 0,( i = 1 to k );
    假设算法返回值true,则有d[vi] <= d[vi-1]+ w( vi-1, vi ),把回路C中这样的式子加起来,得:
    SUM( d[vi] ) <= SUM( d[vi-1] ) + SUM( w(vi-1,vi) ),( i = 1 to k )
    因为 v0 = vk 且是负权回路, 则 SUM( d[vi] ) <= SUM( d[vi-1] ),( i = 1 to k )
    , 则 0 <= SUM( w(vi-1,vi) ),( i = 1 to k ), 
    与题设( SUM( w( vi-1, vi ) ) < 0,( i = 1 to k ) )矛盾
    */
DAG算法

针对有向无回路图,按照节点的拓扑顺序对G( V, E )的边进行松弛

    DAGShortestPath( G, s, w )      //以拓扑顺序对其边进行松弛,在一定程度上是按照最短路径的顺序进行松弛的, T(n) = O(V+E)
    topologically sort the vertex of G ; 
    InitialSingleSource( G, s ) ;
    for eache vertex u in V[G], in topologically sorted order
        for each v in adj[u]
            Relax( u, v, w ) ;
    /*
    由于d[s]=0, 而拓扑排序在s之前的顶点i,有d[i]=MAX_VALUE,所以不会影响d[s]的值,
    ( d[s]=0 <= MAX_VALUE + w(w,s) ),也不会影响任何从s可达的顶点j的d[j]的值
    */
Dijkstra算法

要求有向边的权值非负,即( u, v ) in E有w( u, v ) >= 0. 该算法设置一个顶点集X,从源点s到集合X中的顶点的最短路劲均已确定,算法反复选取具有最短路劲之的顶点u in V-s,并将u加入到X中,对u的所有边进行松弛

    Dijkstra( G, s, w )     //与MSTprime基本一致
        InitialSingleSource( G, s )
        X = NULL ;
        Q = V[G] ;          //以d[u]为关键字的最小优先级队列
        while Q != NULL
            u = ExtractMin( Q ) ;
            X = X U {u} ;
            for each v in adj[u]
                Relax( u, v, w ) ;   //隐含DecreasingKey的操作
    //每次从Q中弹出的都是s可达的具有最短路径的顶点
    //实际上是一种贪心算法
差分约束与最短路径
线性规划

在一般的线性规划问题中,给定一个m*n的矩阵A,一个m维向量b和一个n维向量c,我们希望找出有n个元素组成的向量x,在由 Ax <= b 所给出的m个约束条件下,使目标函数 SUM( ci * xi ),(i = 1 to n )最大 ######差分约束系统 在一个差分约束系统中,线性规划中矩阵A的每一行包含一个 1 和一个 -1,A的所有其他元素都是0,因此,由 Ax <= b 给出的约束条件是 m 个差分约束方程, 形式如下: xj - xi <= bk ( 1 <= i,j <= n, 1 <= k <=m )

|  1 -1  0  0  0 |                      |  0 |          x1-x2 <=  0       
|  1  0  0  0 -1 |      | x1 |          | -1 |          x1-x5 <= -1       
|  0  1  0  0 -1 |      | x2 |          |  1 |          x2-x5 <=  1
| -1  0  1  0  0 |      | x3 |    <=    |  5 |   ===>   x3-x1 <=  5
| -1  0  0  1  0 |      | x4 |          |  4 |          x4-x1 <=  4
|  0  0 -1  1  0 |      | x5 |          | -1 |          x4-x3 <= -1
|  0  0 -1  0  1 |                      | -3 |          x5-x1 <= -3
|  0  0  0 -1  1 |                      | -3 |          x5-x4 <= -3
                                             
        A                 x                b
#设x=( x1, x2, ... , xn )是一个差分约束系统 A*x <= b 的一个解,d为
#任意常数,则 x + d = ( x1+d, x2+d, ..., xn+d )也是该系统的解
约束图

无回路的有向图 G = ( V, E ) 的关联矩阵 B = ( bij ) 是一个 |V| x |E|的矩阵,它满足下列条件:

bij = -1,边j离开顶点i; 1,边j进入顶点i; 0,其他

给定一个查分约束系统 A * x <= b, 相应的约束图是一个带权有向图 G = ( V, E ) ,其中 V = { v0, v1, v2, … , vn },而且 E = { ( vi, vj ) : xj - xi <= bk 是一个约束 } U { (v0, v1), (v0, v2), … , (v0, vn) }

引入附件顶点 v0 是为了保证其每个顶点从 v0 可达, 从 v0 出发的边权值为0 如果G不包含回路,那么 x = ( M(v0, v1), M(v0, v2), … , M(v0, vn) )是此系统的可行解 d[vi] <= d[vj] + w( vj, vi ) ==> d[vi] - d[vj] <= w( vj, vi ) 即 d[vi] 对应 xi, d[vj] 对应 xj, bk 对应 w( vj, vi )

每对定点的最短路径

用邻接矩阵表示图

  1. u ~> v (path p):路径p的权值之和最小
  2. 结果以表格形式给出,第u行第v列是从u到v的最短路劲权值,D = ( d<ij> ),且dij = M( i, j )
  3. 前驱矩阵PI = ( pi<ij> ) : nil, i=j or i到j无路径; 从i出发的某条最短路径上j的前驱定点
  4. 前驱子图: G<pi,i> = ( V<pi,i>, E<pi,i>): V<pi,i> = { j in V : pi<i,j> != nil } & {i}; E<pi,i> = { ( pi<i,j>, j ), j in V<pi,i> - {i} }
    /*
    输出从顶点i到顶点j的一条最短路径
    */
    PrintPairsShortestPath( PI, i, j )
        if i == j
            print i ;
        else if pi<i,j> == nil
            print "No path from i to j" ;
            return ERROR ;
        else 
            PrintPairsShortestPath( PI, i, pi<i,j> ) ;
            print j ;
最短路劲与矩阵乘法

从i到j至多有 n-1 条边, n是顶点的数量 ==> M( i,j ) = l(n-1)<i,j> = l(n)<i,j> = l(n+1)<i,j> = …

最短路径的最优子结构

最短路径的所有子路径也是最短路径

设图以邻接矩阵 W = w<i,j> 来表示

               /  0 ;                i = j
    w<i,j> =  |   有向边(i, j)的权 ; (i,j) in E
               \  MAX_VALUE ;        i != j && (i,j) not in E 
递归解(不含负权回路)

设 l(m)<i,j> 是从顶点i到j至多包含m条边的任何路径的权最小值. 当m = 0时,从i到j存在一条不包含边的路径

                 /  0 ;         i = j
    l(0)<i,j> = |
                 \ MAX_VALUE ;  i != j 

当 m >= 1 时, 计算l(m)<i,j>以及从i到j至多包含m条边的路径的最小权值. 后者是通过计算j的所有可能前驱k而得到的

    l(m)<i,j> = MIN{ l(m-1)<i,j>, MIN( l(m-1)<i,k> + w<k,j>, k from 1 to n ) }
              = MIN{ l(m-1)<i,k> + w<k,j>, k from 1 to n }    
              # w<j,j> = 0     
自底向上计算最短路径的权值

把矩阵 W = w<i,j> 作为输入来计算一组矩阵 L(1), L(2), … L(n-1),其中对于 m >= n 有 L(m) = L(n) = L(n-1), 最后矩阵 L(n-1) 包含实际最短路径的权值

对于所有定点 i,j in V, l(1)<i,j> = w<i,j>, 因此 L(1) = W

    ExtendShortestPath( L, W )      //T(n) = O(n^3)               
        n = row[L] ; 
        /*L的行数,也等于L的列数*/
        make L` an n*n matrix ;

        for i = 1 to n
            for j = 1 to n
                l`<i,j> = l<i,j> ;
                for k = 1 to n
                    if l`<i,j> > l<i,k> + w<k,j>
                        l`<i,j> = l<i,k> + w<k,j> ;
        return L` ;

    /*=================*/    
    MatrixMultiply( A, B )
        n = row[A] ;
        make C an n*n matrix

        for i = 1 to n 
            for j = 1 to n
                c<i,j> = 0 ;
                for k = 1 to n 
                    c<i,j> = c<i,j> + a<i,k> * b<k,j> ;

        return C ;

    /*====================*/
    SlowAllPairsShortestPaths( W )  //T(n) = O( V^4 )
        L(1) = W ;
        n = row[W] ;

        for i = 2 to n-1
            L(i) = ExtendShortestPath( L(i-1), W ) ;

        return L(n-1) ;

对比矩阵乘法可发现:

L(1) = L(0) * W = W, L(2) = L(1) * W = W^2, … , L(n-1) = L(n-2) * W = W^(n-1)

改进运行时间,由于 ExtendShortestPath 与矩阵乘法相似,可以也满足乘法的结合律,所以只需要计算 lg(n-1) 个矩阵就能计算出L(n-1)

L(1) = L(0) * W, L(2) = L(1) * L(1), L(4) = L(2) * L(2)

    FastAllPairsShortestPaths( W )   //T(n) = O( V^3 * lgV ) 
        L(1) = W ;
        n = row[W] ;
        m = 1 ;

        while m < n 
            L(2m) = ExtendShortestPath( L(m), L(m) ) ;
            m = 2*m ;

        return L(m) ;
FloydWarShall算法

不含负权回路

结构

中间节点:简单路劲 P=<v1, v2, … , vl> 上的中间顶点,是除v1和vl以外的p上的任意顶点,即<v2, v3, …, vl-1>

递归解

令d(k)<i,j>为顶点i到j且满足所有中间顶点属于集合{1,2, …, k}的一条最短路劲的权值

                /   w<i,j> ;            k=0
    d(k)<i,j> = |
                \   MIN( d(k-1)<i,j>, d(k-1)<i,k> + d(k-1)<k,j> )

    最终: d(n)<i,j> = M(i,j) ;
实现
    FloydWarShall( W )   //T(n) = O(n^3)
        D(0) = W ;
        n = row[W] ;

        for k = 1 to n
            for i = 1 to n 
                for j = 1 to n 
                    d(k)<i,j> = MIN( d(k-1)<i,j>, d(k-1)<i,k> + d(k-1)<k,j> ) ;
        
        return D(n) ;
构造一条最短路径

定义PI(k)<i,j>为从i出发的一条最短路径上顶点j的前趋,而这条路劲上的中间顶点属于集合{1,2, …, k} .

    当k=0时,易知
                 / nil ; i = j or w<i,j> = MAX_VALUE
    PI(0)<i,j> = |
                 \ i ;  i != j and w<i,j> < MAX_VALUE

    当k >= 1 时
                 / PI(k-1)<k,j> ;  d(k-1)<i,j> > d(k-1)<i,k> + d(k-1)<k,j>
    PI(k)<i,j> = |
                 \ PI(k-1)<i,j> ;  d(k-1)<i,j> > d(k-1)<i,k> + d(k-1)<k,j>
有向图的传递闭包

定义: G* = ( V, E* ),其中E* = { (i, j) : 图中存在一条从i到j的路径}

    在传递闭包中
              / 1 ; i = j or (i,j) in E
    w<i,j> = |
              \ 0 ; i != j and (i,j) not in E 

    d(k)<i,j> = d(k-1)<i,j> or ( d(k-1)<i,k> and d(k-1)<k,j> ) 
    当 d(k)<i,j> = 1 时, 将(i,j)加入E*
稀疏图上的johnson算法

对每对顶点使用 Dijkstra 算法,来找出每对顶点的最短路径.这就要求w非负,要对w重付权,以保证w非负

返回:最短路径权值矩阵 or ERROR(存在负权回路)

重付权,设 G = (V,E) 的加权函数 w : E -> R
    1. 保持最短路径: 重付权 w`( u, v ) = w( u, v) + h(u) - h(v)
    
    2. 非负:
        构造一个新图
                           / V` = V U { s : s not in V }
        G` = ( V`, E` ) : |  E` = E U { (s,v) : v in V }
                           \ w(s,v) = 0, 其中 v in V 

        h(v) = M(s,v), 其中 v in V
        ==> h(v) <= h(u) + w(u,v), 其中 (u,v) in E`
        ==> w`( u, v ) = w( u, v) + h(u) - h(v) >= 0
实现
    Johnson( G )    // T(n) = O( VElgV )
                                / V` = V[G] U { s : s not in V[G] }       ;
        make G` = ( V`, E` ) : |  E` = E[G] U { (s,v) : v in V[G] }       ;
                                \ W` = W[G] U { w(u,v) = 0 : V in V[G] }  ;

        make D an n*n matrix, n = |V| ; 

        if bellmanFord( G`, s, W` ) == false
            print "there are some regative-weigth cucles" ;
            return ERROR ;

        for each vertex u in V[G]
            h[u] = M(s, u) computed by bellmanFord in G` ;

        for each edge ( u, v ) in E[G]
            w`(u,v) = w(u,v) + h[u] - h[v] ;

        for each vertex u in V[G] 
            run Dijkstra( G, u, w` ) to compute all M`(u, v) for v in V[G] ;

        for each vertex v in V[G]
            d<u,v> = M`( u, v ) + h[v] - h[u] ;

        return D ;

流网络

流网络和流
              / G = (V, E), 且|E| >= |V|-1, 即G是连通图
    流网络 : |  非负容量 c<u,v>: 大于等于0,(u,v) in E; 等于0,(u,v) not in E 
              \ 原点s和汇点t 


          / 实值函数 f: v x v -> R
    流 : |          /  i. f(u,v) <= c(u,v) (容量限制) -- u, v in V 
         |  性质 :|  ii. f(u,v) = -f(v,u) (反对称性) /
          \         \iii. SUM( f(u,v); v in V ) = 0 (流守恒) u in V - {s, t}

    |f| = SUM( f(s,v); v in V ) : 从源点出发的总流

    SUM( f(u,v); f(u,v)>0 and u in V ) : 进入v的总的正流
具有多个源点和汇点的网络
                                                 
    s1                              s1     
       \                        /      \                
        - t1                   /        - t1        
       /                      /        /     \
    s2             ===>    S  ---   s2        - T
       \                      \        \     /       
        - t2                   \        - t2      
       /                        \      /     
    s3                              s3      

    且从新增源点S到s1,s2, ..., si的容量c为MAX_VALUE
    从t1,t2, ..., ti到新增汇点T的容量c为MAX_VALUE
    其他路径容量不变
对流的处理

设X,Y是顶点集合, 令f(X,Y) = SUM( f(x,y); x in X, y in Y ),则流守恒可表述为:对 u in V - {s, t}, f(u,V) = 0

    f(X,X) = 0; X包含于V
    f(X,Y) = -f(Y,X); X,Y包含于V

    f(X U Y, Z) = f(X,Z) + f(Y,Z)  ; X,Y,Z包含于V
    f(Z, X U Y) = f(Z,X) + f(Z,Y)  ; 且 X 交 Y = NULL
FordFalkerson方法

开始时: f(u,v) = 0; u,v in V. 迭代: 通过找出一条”增广路径”来增加流值

    FordFalkersonMethod( G, s, t )
        initialize flow f to 0 ;

        while there exists an augmenting path p
            augment flow f along p ;

        return f ;
残留网络

Gf( V, Ef ), 其中Ef为{ (u,v) in V x V, cf(u,v) > 0 }. cf(u,v) = c(u,v) - f(u,v), 即(u,v)的残留容量

          / (u,v) in E -- cf(u,v) = c(u,v) - f(u,v)
    Ef = |             \  cf(v,u) = c(v,u) - f(v,u)
          \ (u,v) not in E -- c(u,v) = c(v,u) = f(u,v) = f(v,u) = 0
      |
      v
    |Ef| = 2|E|
增广路径

增广路径p为残留网路Gf中从s到t的一条简单路径 且 cf(p) = min{ cf(u,v):(u,v)在p上}

流网络的割

将V划分为S和T=V-S,使得 s in S, t in T

注意:流经任意个的净流都是相同的,且与流的值相等.网络的最大流必定不超过此网络最小割的容量

基本的FordFalkerson算法
    FordFalkerson( G, s, t )  //T(n) = O(E|f*|),其中f*是算法找出的最大流
        for each edge (u, v) in E[G]
            f(u, v) = f(v, u) = 0 ;

        while there exists a path p from s to t in the residual network Gf
            Gf(p) = MIN( cf(u,v) : (u,v) in path p ) ;
            for each (u,v) in p
                f(u,v) = f(u,v) + cf(p) ;
                f(v,u) = - f(u,v) ;
EdwardsKarp算法

用广度优先搜索来实现增广路径p的计算,可对FordFalkerson方法进行改进,使得T(n)=O(VE^2)

最大二分匹配

给定一个无向图G=(V,E)

二分匹配假定集合可被划分为 V = L U R, 其中 L交R = NULL, 且E中所有边的一个顶点在R中,另一端在L中,

匹配(N):顶点只与一条边关联.转化为最大流问题,可在O(VE)的时间内找到. 在二分匹配加入源点s和汇点t,且s和L中的顶点相连,R中的顶点和t相连,每条边赋予单位容量.那么s到t的最大流就是最大二分匹配的个数.

压入与重标记算法
前置流
    f : V x V -> R
    对称性
    容量限制
                       / f(V, u) >= 0, u in V-{s}:进入定点u的余流
    放宽条件的流守恒性 |
                       \ e[u] > 0, 则称顶点u溢出
顶点高度

h[s] = |V|, h[t] = 0 ; 余流只能从高流向低

基本操作
  1. 把流的余量从一个顶点压入到它的一个相邻顶点
  2. 重标记一个顶点(调整顶点的高度)

压入操作:如果u是某溢出顶点, cf(u,v) > 0, 且h[u] = h[v]+1, 则可应用基本操作Push(u, v)

    /*
    饱和压入 : cf(u,v) = 0, 顶点u还可能溢出
    不饱和压入:cf(u,v) > 0, 顶点u不再溢出 
    */
    Push( u, v )
        df(u,v) = min( cf(u,v), e[u] ) ;

        f(u,v) = f(u,v) + df(u,v) ;
        f(v,u) = -f(v,u) ;
        e[u] = e[u] - df(u,v) ;
        e[v] = e[v] + df(u,v) ;

        cf(u,v) = cf(u,v) - df(u,v) ;
        cf(v,u) = cf(u,v) + df(u,v) ;

重标记操作:1.顶点u是溢出顶点; 2.(u,v) in Ef; 3.h[u] <= h[v]

    Relabel( u )
        h[u] = min( h[v]+1 : (u,v) in Ef ) ;
一般性算法
    InitializePreflow( G, s )
        for echi vertex u in V[G]
            e[u] = 0 ;
            h[u] = 0 ;
        h[s] = |V| ;

        for each edge (u,v) in E[G]
            f(u,v) = f(v,u) = 0 ;

        for echo u in adj[s]
            e[u] = c(s,u) ;
            f(s,u) = e[u] ;
            f(u,s) = -e[u] ;
            cf(u,s) = e[u] ;
            cf(s,u) = 0 ;

    /*========*/
    GenericPushRelabel( G, s, t )    //T(n) = O(V^2 * E) 
        InitializePreflow( G, s ) ;

        while 存在可执行的PushRelabel操作
            随便选出一个PushRelabel操作执行,Push操作具有高优先执行权;
  1. 循环不变式:每次执行while循环,f都是一个前置流
  2. 初始化:InitializePreflow( G, s )初始化f为前置流
  3. 保持:while循环中,重标记操作对流无作用,压入操作时,保持f是前置流
  4. 终止: V - {s,t} 中每个顶点的余流为0,网络中没有溢出顶点,f是一个流
重标记与前移算法
                            反复            直到
顶点表 ------> 从前端扫描 ------> 溢出顶点 ------> 余流 
                            选出     |     不存在
                                     |
                                     |
                                     V
                        即反复执行压入和重标记操作
                                           |
                                           V
                                    且将进行过重标记
                                    操作的顶点移动到
                                    顶点表的前段
容许边和容许网络
               / s:源点
    G = (V, E) | t:汇点
               | f:前置流
               \ h:高度函数
  1. 容许边: cf(u,v) > 0 且 h[u] = h[v] + 1,则(u,v)是容许边
  2. 容许网络:G<f,h> = ( V, E<f,h> ), E<f,h>是容许边的集合,容许网络中不含回路
相邻表

N[u]是关于G中顶点u的相邻定点的单链表.因此,如果(u,v) in E 或者 (v, u) in E, 则顶点v出现在N[u]中

N[u]: head[N[u]],第一个顶点; next_neighbor[n],下一个顶点; current[u],当前被考察的顶点.

    Discharge( u )
        current[u] = head[N[u]] ;
        while e[u] > 0
            v = current[u] ;
            if v == nil 
                Relabel( u ) ;
                current[u] = head[N[u]] ;
            else if cf(u,v) > 0  and  h[u] == h[v]+1
                Push( u, v ) ;
            else
                current[u] = next_neighbor[n] ;
实现

链表 L = V-{s,t}

next[u]:链表L中节点u的下一个节点.如等于nil,则u是L的最后一个节点

假设对每个顶点u已建立了相邻表N[u]

    RelabelToFront( G, s, t )            //T(n) = O(V^3)
        InitializePreflow( G, s ) ;
        L = V[G] - {s, t} ;
        u = head[L] ;

        while u != nil
            old_height = h[u] ;
            Discharge( u ) ;
            if( h[u] > old_height )      //u被重标记过
                move u to the front of L ;
            u = next[u] ;
  1. 循环不变式:链表L存放了容许网络 G<f,h> = ( V, E<f,h> ) 中被拓扑排序的顶点,而且在链表中,u之前的节点都没有余流.
  2. 初始化:运行 InitializePreflow 后,h[s] = V , v in V-{s} 有h[v] = 0,且 E<f,h> = NULL, 没有容许边 ===> V - {s,t}的任意序列都是 G<f,h> 的一个拓扑排序.易知,没有余流在u之前.
  3. 保持:压入操作不能将边变成容许变,重标记操作可以产生容许边,而顶点u被重标记后,不会产生进入u的容许变,但可能产生离开u的容许边,所以将u移动到L的前端.算法保持任意离开u的容许边都满足拓扑排序.易知,没有余流在u之前.
  4. 终止:u到了L末端,循环不变式确保每个定点的余流都为0,问题得解