图论总结(超强大)

ADN.cnlibrarysummary 图论总结 2022-2-221.图论 Graph Theory1.1.定义与术语 Definition and Glossary1。1。1.图与网络 Graph and Network1.1。2。图的术语 Glossary of Graph1.1.3.路径与回路 Path and Cycle1.1.4。连通性 Connectivity1.1.5。图论中特殊的集合 Sets in graph1.1。6.匹配 Matching1。1。7.树 Tree1。1.8。组合优化 Combinatorial optimization1.2。图的表示 Expressions of graph1.2.1.邻接矩阵 Adjacency matrix1。2.2.关联矩阵 Incidence matrix1.2.3。邻接表 Adjacency list1.2。4。弧表 Arc list1.2.5.星形表示 Star1。3。图的遍历 Traveling in graph1.3.1。深度优先搜索 Depth first search (DFS)1.3.1.1.概念1。3.1。2。求无向连通图中的桥 Finding bridges in undirected graph1。3.2.广度优先搜索 Breadth first search （BFS）1.4。拓扑排序 Topological sort1.5。路径与回路 Paths and circuits1.5。1.欧拉路径或回路 Eulerian path1。5。1。1。无向图1。5。1。2。有向图1.5。1.3。混合图1.5。1.4。无权图 Unweighted1。5。1.5.有权图 Weighed 中国邮路问题The Chinese post problem1。5。2。Hamiltonian Cycle 哈氏路径与回路1.5.2.1。无权图 Unweighted1。5。2.2.有权图 Weighed - 旅行商问题The travelling salesman problem1。6.网络优化 Network optimization1。6。1。最小生成树 Minimum spanning trees1.6。1。1。基本算法 Basic algorithms1。6。1。1。1.Prim1.6.1.1。2.Kruskal1.6。1.1。3.Sollin（Boruvka）1.6.1。2。扩展模型 Extended models1.6.1.2。1。度限制生成树 Minimum degreebounded spanning trees1。6。1.2。2。k小生成树 The k minimum spanning tree problem(kMST)1。6。2.最短路Shortest paths1。6。2。1.单源最短路 Singlesource shortest paths1.6。2.1。1。基本算法 Basic algorithms1。6.2.1.1.1。Dijkstra1.6。2。1.1.2。BellmanFord1。6.2.1.1。2。1.Shortestpathfasteralgorithm(SPFA)1。6.2.1。2。应用Applications1.6。2。1.2.1。差分约束系统 System of difference constraints1。6。2.1.2.2.有向无环图上的最短路 Shortest paths in DAG1。6。2。2.所有顶点对间最短路 All-pairs shortest paths1。6。2。2.1.基本算法 Basic algorithms1.6。2.2。1。1.Floyd-Warshall1.6。2。2。1.2.Johnson1。6.3.网络流 Flow network1。6。3.1.最大流 Maximum flow1.6.3.1.1.基本算法 Basic algorithms1.6。3.1。1。1.Ford-Fulkerson method1。6.3.1.1。1.1。Edmonds-Karp algorithm1。6.3。1。1.1.1.1。Minimum length path1。6.3。1.1.1。1.2。Maximum capability path1。6.3.1.1。2.预流推进算法 Preflow push method1.6.3。1。1.2。1。Push-relabel1.6.3.1.1.2。2.Relabelto-front1。6。3。1.1。3.Dinic method1。6。3。1。2.扩展模型 Extended models1。6.3。1。2。1.有上下界的流问题1.6.3.2。最小费用流 Minimum cost flow1。6.3.2.1.找最小费用路 Finding minimum cost path1。6。3.2.2.找负权圈 Finding negative circle1。6。3.2。3.网络单纯形 Network simplex algorithm1。6.4.匹配 Matching1。6。4.1.二分图 Bipartite Graph1。6.4。1.1.无权图匈牙利算法 Unweighted Hopcroft and Karp algorithm1。6。4.1.2。带权图KM算法 Weighted Kuhn-Munkres(KM) algorithm1。6。4.2.一般图General Graph1.6.4。2。1。无权图带花树算法 Unweighted - Blossom (Edmonds）1. 图论 Graph Theory1.1. 定义与术语 Definition and Glossary1.1.1. 图与网络 Graph and Network二元组称为图(graph)。为结点(node）或顶点（vertex）集。为中结点之间的边的集合。点对称为边（edge)或称弧(arc），其中，称是相邻的（adjacent），称u，v与边相关联(incident）或相邻。若边的点对有序则称为有向(directed）边，其中u称为头（head)，v称为尾(tail）。所形成的图称有向图（directed graph)。为对于u来说是出边（outgoing arc);对于v来说是入边(incoming arc)。反之，若边的点对无序则称为无向(undirected)边，所形成的图称无向图（undirected graph)。若图的边有一个权值(weight),则称为赋权边，所形成的图称赋权图（weighted graph）或网络(network)。用三元组G(V,E,W）表示网络。其中W表示权集，它的元素与边集E一一对应。满足的图，称为稀疏（sparse)图；反之，称为稠密(dense)图。1.1.2. 图的术语 Glossary of Graph阶（order):图G中顶点集V的大小称作图G的阶。环(loop）：若一条边的两个顶点为同一顶点,则此边称作环。简单图（simple graph）：没有环、且没有多重弧的图称作简单图.定向图:对无向图G的每条无向边指定一个方向得到的有向图。底图：把一个有向图的每一条有向边的方向都去掉得到的无向图。逆图:把一个有向图的每条边都反向由此得到的有向图。竞赛图(tournament）：有向图的底图是无向完全图,则此有向图是竞赛图。邻域(neighborhood）:在图中与u相邻的点的集合,称为u的邻域，记为。度：度(degree）：一个顶点的度是指与该边相关联的边的条数，顶点v的度记作deg(v）。握手定理：无向图：；有向图:。入度（indegree)：在有向图中,一个顶点v的入度是指与该边相关联的入边（即边的尾是v）的条数，记作。出度(outdegree)：在有向图中，一个顶点的出度是指与该边相关联的出边（即边的头是v)的条数,记作。孤立点(isolated vertex)：度为0的点.叶(leaf)：度为1的点.源(source）:有向图中，=0 的点。汇（sink)：有向图中,=0的点。奇点（odd vertex）:度为奇数的点。偶点（even vertex)：度为偶数的点.子图：子图（sub-graph)：G称作图G的子图如果以及。生成子图(spanning sub-graph)：即包含G 的所有顶点的连通子图，即满足条件的G的子图G。生成树（spanning tree）：设T是图G的一个子图，如果T是一棵树，且,则称T是G的一个生成树。即G的生成子图，且子图为树.点导出子图(induced subgraph)：设,以为顶点集，以两端点均在中的边的全体为边集所组成的子图,称为G的由顶点集导出的子图，简称为G的点导出子图，记为。边导出子图(edgeinduced subgraph)：设，以为顶点集，以两端点均在中的边的全体为边集所组成的子图，称为G的由边集导出的子图，简称为G的边导出子图，记为。图的补图(complement）：设G是一个图,以为顶点集，以为边集的图称为G的补图，记为。点集的补集:记 为点集的补集.特殊的图:零图（null graph):，即只有孤立点的图.n阶零图记为。平凡图(trivial graph)：一阶零图.空图（empty graph):的图。有向无环图（directed acyclic graph(DAG）)：有向的无环的图.完全图（complete graph)：完全图是指每一对不同顶点间都有边相连的的无向图，n阶完全图常记作。二分图（bipartite graph）:若图G的顶点集可划分为两个非空子集X和Y,即且,且每一条边都有一个顶点在X中,而另一个顶点在Y中，那么这样的图称作二分图。完全二分图(complete bipartite graph)：二分图G中若任意两个X和Y中的顶点都有边相连，则这样的图称作完全二分图。若，则完全二分图G记作。正则图(regular graph）：如果图中所有顶点的度皆相等，则此图称为正则图。1.1.3. 路径与回路 Path and Cycle途径（walk)：图G中一个点边交替出现的序列，满足,.迹（trail)：边不重复的途径.路(path）：顶点不重复的迹。简单图中的路可以完全用顶点来表示,。若，称闭的(closed）；反之，称为开的（open）。闭途径(closed walk)：起点和终点相同的途径。闭迹（closed trail）：起点和终点相同的迹，也称为回路（circuit）。圈(cycle）：起点和终点相同的路.途径（闭途径)、迹（闭迹）、路（圈)上所含的边的个数称为它的长度（length）。简单图G中长度为奇数和偶数的圈分别称为奇圈(odd cycle）和偶圈(even cycle）.对任意，从x到y的具有最小长度的路称为x到y的最短路(shortest path)，其长度称为x到y的距离（distance)，记为。图G的直径(diameter）:。简单图G中最短圈的长度称为图G的围长（girth)，最长圈的长度称为图G的周长（perimeter)。1.1.4. 连通性 Connectivity连通(connected)：在图G中,两个顶点间，至少存在一条路径,称两个顶点连通的(connected);反之，称非连通(unconnected）.强连通(strongly connected）：在有向图G中,两个顶点间,至少存在一条路径，称两个顶点强连通。弱连通（weakly connected)：在有向图G中，两个顶点间，若不考虑G中边的方向的图才连通的，称原有向图为弱连通。连通图(connected graph）：图G中任二顶点都连通.连通分量或连通分支（connected branch， component)：非连通无向图的极大连通子图（maximally connected sub-graph）。具体说，若图G的顶点集V(G）可划分为若干非空子集，使得两顶点属于同一子集当且仅当它们在G中连通，则称每个子图为图G的一个连通分支（）。图G的连通分支是G的一个极大连通子图。图G连通当且仅当。强连通分量（strongly connected branch）:非强连通图有向图的极大强连通子图。割(cut)：点割集（vertex cut）：点集，若G删除了后不连通，但删除了的任意真子集后G仍然连通.则称点割集。若某一结点就构成就了点割集,则称此结点割点(cut vertex）。点数最少的点割集称为点连通度k(G）.边割集（edge cut set):边集，若G删除了后不连通，但删除了的任意真子集后G仍然连通。则称点割集。若某一边就构成就了边割集，则称此结点割边（cut edge）或桥(bridge）.边数最少的边割集称为边连通度k（G）。记号表示一端在S中另一端在中的所有边的集合。块(block）是指没有割点的极大连通子图。1.1.5. 图论中特殊的集合 Sets in graph点覆盖(集)(vertex covering （set）)：，满足对于，有，关联。即一个点集,使得所有边至少有一个端点在集合里.或者说是“点 覆盖了所有“边”。极小点覆盖（minimal vertex covering）:本身为点覆盖,其真子集都不是。最小点覆盖（minimum vertex covering）：点最少的点覆盖。点覆盖数(vertex covering number):最小点覆盖的点数,记为一般说覆盖集就是指点覆盖集.边覆盖(集)（edge covering （set）：,满足对于，有，关联。即一个边集，使得所有点都与集合里的边邻接。或者说是“边” 覆盖了所有“点”。 极小边覆盖(minimal edge covering）：本身是边覆盖，其真子集都不是。最小边覆盖（minimum edge covering）:边最少的边覆盖。边覆盖数(edge covering number)：最小边覆盖的边数，记为。独立集（independent set）：,满足对于,有.即一个点集，集合中任两个结点不相邻,则称为独立集。或者说是导出的子图是零图（没有边）的点集。极大独立集（maximal independent set）：本身为独立集，再加入任何点都不是。最大独立集（maximum independent set）：点最多的独立集。独立数(independent number）：最大独立集的点数，记为.团（clique）：，满足对于,有。即一个点集,集合中任两个结点相邻。或者说是导出的子图是完全图的点集。极大团(maximal clique）：本身为团，再加入任何点都不是。最大团(maximum clique)：点最多的团。团数（clique number)：最大团的点数，记为。边独立集(edge independent set)：，满足对于，有不邻接。即一个边集，满足边集中的任两边不邻接。极大边独立集（maximal edge independent set)：本身为边独立集，再加入任何边都不是。最大边独立集(maximum edge independent set)：边最多的边独立集。边独立数（edge independent number):最大边独立集的边数，记为。边独立集又称匹配(matching),相应的有极大匹配(maximal matching），最大匹配(maximum matching)，匹配数（matching number）。支配集（dominating set)：，满足对于，有,。即一个点集，使得所有其他点至少有一个相邻点在集合里.或者说是一部分的“点”支配了所有“点”. 极小支配集（minimal dominating set）：本身为支配集，其真子集都不是.最小支配集(minimum dominating set）：点最少的支配集。支配数(dominating number)：最小支配集的点数，记为。边支配集(edge dominating set）:，满足对于，有，邻接。即一个边集,使得所有边至少有一条邻接边在集合里。或者说是一部分的“边”支配了所有“边.极小边支配集（minimal edge dominating set）：本身是边支配集，其真子集都不是.最小边支配集(minimum edge dominating set）:边最少的边支配集。边支配数(edgedominating number)：最小边支配集的边数，记为. 定理：若G中无孤立点，D为支配集，则D=V(G）D也是一个支配集。定理:一个独立集是极大独立集，当且仅当它是支配集。关系：定理：无向图G无孤立点，是极小支配集,则存在是极小支配集，且。定理：无向图G无孤立点，是极大独立集，则是极小支配集。逆命题不成立。定理：连通图中，是点覆盖，则是支配集。极小点覆盖不一定是极小支配集。支配集不一定是点覆盖。定理:无向图G无孤立点,是（极，最小)点覆盖,充要于是（极，最大）独立集。定理：无向图G，是G的(极，最大)团，充要于是的（极，最大）独立集。.由上述定理知，三者互相确定，但都是NPC的。但是二分图中，点覆盖数是匹配数。M是匹配，W是边覆盖，N是点覆盖,Y是点独立集。定理:无向图G无孤立点，|M=N，Y|=|W定理：无向图G无孤立点,。先取一个最大匹配M，1条边盖两个点；剩下的一个未盖点要用一条边来覆盖，边覆盖数=M +(V-2|M）= |V|-|M|。定理：无向图G无孤立点，=,=。定理:无向图G无孤立点,=。求匹配数是P的，所以边覆盖和匹配都是易求的。最小路径覆盖(path covering)：是“路径” 覆盖“点，即用尽量少的不相交简单路径覆盖有向无环图G的所有顶点，即每个顶点严格属于一条路径.路径的长度可能为0(单个点）.最小路径覆盖数G的点数最小路径覆盖中的边数。应该使得最小路径覆盖中的边数尽量多，但是又不能让两条边在同一个顶点相交。拆点:将每一个顶点i拆成两个顶点Xi和Yi。然后根据原图中边的信息，从X部往Y部引边。所有边的方向都是由X部到Y部.因此，所转化出的二分图的最大匹配数则是原图G中最小路径覆盖上的边数.因此由最小路径覆盖数原图G的顶点数二分图的最大匹配数便可以得解.1.1.6. 匹配 Matching匹配（matching)是一个边集，满足边集中的边两两不邻接。匹配又称边独立集(edge independent set)。在匹配中的点称为匹配点(matched vertex）或饱和点；反之,称为未匹配点(unmatched vertex）或未饱和点。交错轨（alternating path）是图的一条简单路径，满足任意相邻的两条边，一条在匹配内，一条不在匹配内。增广轨(augmenting path)：是一个始点与终点都为未匹配点的交错轨.最大匹配(maximum matching）是具有最多边的匹配。匹配数（matching number）是最大匹配的大小。完美匹配(perfect matching)是匹配了所有点的匹配。完备匹配（complete matching）是匹配了二分图较小部份的所有点的匹配。增广轨定理：一个匹配是最大匹配当且仅当没有增广轨。综上，在二分图中,最小覆盖数=最大匹配数。边覆盖数=最大独立数=|V最大匹配数。1.1.7. 树 TreeG=（V， E）为一个图，则下列命题等价：(1）G是一棵树；(2)G连通，且E|=|V1;（3)G无圈，且E=|V|-1；(4）G的任何两个顶点之间存在唯一的一条路；（5)G连通，且将G的任何一条弧删去之后，该图成为非连通图；(6）G无圈,且在G的任何两个不相邻顶点之间加入一条弧之后,该图正好含有一个圈.Cayley公式：在n阶完全图中,不同生成树的个数为。1.1.8. 组合优化 Combinatorial optimization从若干可能的安排或方案中寻求某种意义下的最优安排或方案,数学上把这种问题称为(最)优化（optimization）问题。所谓组合（最）优化(combinatorial optimization）又称离散优化(discrete optimization）,它是通过数学方法去寻找离散事件的最优编排、分组、次序或筛选等。 这类问题可用数学模型描述为：其中D表示有限个点组成的集合（定义域），f为目标函数，为可行域。网络优化(network optimization)就是研究与(赋权)图有关的组合优化问题.常见的P类网络优化问题：最小生成树，最短路，最大流,最小费用最大流，最大匹配，中国邮路问题.常见的NP类网络优化问题：旅行商问题。参考文献：1Dictionary of Algorithms and Data Structures NIST,http:/www.nist。gov/dads/2Wikipedia，http:/en。wikipedia。org/wiki/Graph_theory3谢金星，清华大学数学科学系讲义http:/faculty.math.tsinghua。edu。cn/jxie/courses/netopt1.2. 图的表示 Expressions of graph下面介绍几种表示图的数据结构。并统一用下图做例子:12345123786541.2.1. 邻接矩阵 Adjacency matrix用二元数组，来表示图。这种表示法一般用于稠密图。当图不是简单图,邻接矩阵法不能用。在无权图中，若边存在，=1；否则=0。无权图的例子:在有权图中, 若边存在，则为它的权值；否则人为的规定=或。是一个足够大的数.无向图中，邻接矩阵是按矩阵副对角线对称的。1.2.2. 关联矩阵 Incidence matrix用二元数组，来表示无权有向图。一般不用这种表示法。若边k与点u关联，若k是u的出边，则=1；若k是u的入边=1；否则=0。无权图的例子:1.2.3. 邻接表 Adjacency list图的邻接表是图的所有节点的邻接表的集合；而对每个节点,它的邻接表就是它的所有出弧的集合,含有终点，权值等信息。对于有向图G=(V，E），一般用A(v）表示节点v的邻接表，即节点v的所有出弧构成的集合或链表（实际上只需要列出弧的另一个端点，即弧的尾)。一般图都适用.邻接表方法增加或删除一条弧所需的计算工作量很少。有权图的例子：A(1)=2，3，A(2）=4，A(3）=2，A（4）=3,5，A(5)=3，412345283904602403053036470终点权值指针起点1.2.4. 弧表 Arc list所谓图的弧表， 也就是图的弧集合中的所有有序对以表格的方式来表示.弧表表示法直接列出所有弧的起点和终点，以及权值。一般用于稀疏图。缺点是无法通过一些信息（起点，终点)定位一条边。用S（i）,F(i），W(i）分别表示起点，终点，权值。有权图的例子:起点13455421终点22543343权值843760691.2.5. 星形表示 Star星形表示法就是对弧表的缺点的改进，使之可以通过起点或终点定位边。由于很多时候,算法只需事先知道起点，通过枚举边扩展，而不需要事先知道终点；如图的遍历，松弛操作。按定位方式，又分前向星形（forwards star）与反向星形（reverse star）。前向星形:通过起点定位边。反向星形：通过终点定位边。实际上，反向星形几乎没用。故本文只讨论前向星形。通常有两种方法实现这种对弧表改进:边排序法，链表法。边排序法：把弧表按起点为第一关键字,终点为第二关键字来排序。排序用不用额外空间的快速排序O(mlogm)或用额外空间O(m)的计数排序O(m）均可。之后用数组last（u）记录以结点u为起点的最后一条边的编号,并规定last(0）=0。这样以结点u为起点的边编号就是last(u1)+1到last(u)。有权图的例子:作为起点的点012345最后边的编号023468编号12345678起点11234455终点23423534权值89640367链表法：给每条边(u,v）加一个前趋，表示以u为起点的边链表的前一条边。直观的讲，就是将相同结点的边用链表串起来.last(u）存以u为起点的最后一条边的编号。有权图的例子：作为起点的点12345最后边的编号65278编号012345678起点nil53412145终点nil42524333权值nil74386906前趋nil00000431星形表示法的优点是占用的存贮空间较少。一般图都适用.边排序法的优点是已知起点和终点的情况下可以精确定位边，容易在起点定位的范围内二分查找终点，在反向边的定位中常用；缺点是代码麻烦，时间抑或空间上都有额外开销。链表法的优点很多，不仅代码简单，而且没有太多的时空开销，对于反向边的定位只要多加一个数据项纪录下反向边即可；除了终点定位性，几乎没缺点。参考文献：1谢金星,清华大学数学科学系讲义http:/faculty。math.tsinghua.edu。cn/jxie/courses/netopt2刘汝佳,黄亮，算法艺术与信息学竞赛，P601.3. 图的遍历 Traveling in graph1.3.1. 深度优先搜索 Depth first search (DFS）1.3.1.1. 概念1.3.1.2. 求无向连通图中的桥 Finding bridges in undirected graph在无向连通的条件下，边是桥的充要条件是：1.桥一定是DFS树中的边；2.桥一定不在圈中。圈是由一条后向边（u，v)与DFS树中u到v的路径组成。也就是说u到v的路径上的边都不可能是桥，应该给以标记。记f（x)为x与其子孙的后向边所连到的最老祖先(深度最浅）,表示x 到f（x) 上的边均不为桥。然而维护f（x）比较麻烦,其实只要知道f（x)的拓扑序数就可以了。所谓拓扑序数就是满足儿子的序数总比父亲大的一个编号方式。这个拓扑序，常用使用深度d，或者使用时间戳(TimeStamp） DFN（DFS访问的次序）.下面以深度为例：记，在DFS树中从x开始通过前向弧和后向弧所能到达的最小的d。有以下的动态规划：这里：1。第一次访问x时，记录d（x)2。 d（y)自己发出去的后向边所达到的深度。3. g（c）就是其子孙中的g最小值。最后,若g(x）=d(x)，即(father，x）不在圈中,则(father， x)就是桥.1.3.2. 广度优先搜索 Breadth first search （BFS）1.4. 拓扑排序 Topological sort拓扑排序是对有向无圈图（DAG）顶点的一种排序,它使得如果存在u,v的有向路径,那么满足序中u在v前。拓扑排序就是由一种偏序(partical order）得到一个全序(称为拓扑有序（topological order）)。偏序是满足自反性，反对称性,传递性的序。拓补排序的思路很简单，就是每次任意找一个入度为0的点输出,并把这个点以及与这个点相关的边删除.实际算法中，用一个队列实现.算法：1. 把所有入度=0的点入队Q。2. 若队Q非空，则点u出队，输出u；否则转4。3. 把所有与点u相关的边（u，v)删除，若此过程中有点v的入度变为0，则把v入队Q，转2。4. 若出队点数=n（含有负圈)。由于点可能多次入队，但队列中同时不会超过n个点。所以用一个长度为n的循环队列来实现这个队。SPFA在形式上和宽度优先搜索非常类似,不同的是宽度优先搜索中一个点出了队列就不可能重新进入队列,但是SPFA中一个点可能在出队列之后再次被放入队列，也就是一个点改进过其它的点之后,过了一段时间可能本身被改进，于是再次用来改进其它的点,这样反复迭代下去。设一个点用来作为迭代点对其它点进行改进的平均次数为k，有办法证明对于通常的(不含负圈，较稀疏）情况，k在2左右。算法复杂度理论上同Bellman-Ford，O（nm)，但实际上却是O(km）。一般用于找负圈(效率高于BellmanFord），稀疏图的最短路.习题:Ural 1254 Die Hard （可斜走的网格最短路）。1.6.2.1.2. 应用Applications1.6.2.1.2.1. 差分约束系统 System of difference constraints差分约束系统：求解n个未知数，满足m个不等式：若描述为线形规划模型：.矩阵A每行含一个1一个1,其他都是0.如线形规划模型等价于注意到单源最短路模型中的。，即。很像差分约束系统模型。于是可以构造一个有向网络G=(V,E，W),称为约束图(constraints graph）。.W：，对进行BellmanFord算法，可以得到，令，即为所求，其中C是任意一个常数，均满足原不等式组。当有为负数且题目要求非负时,常常令C为最小的的相反数。习题：NOI 1999 01串1.6.2.1.2.2. 有向无环图上的最短路 Shortest paths in DAG算法：1. ，.对有向无环图G，拓扑排序O(m）.2。按拓扑序枚举u。若枚举完，则结束。3.枚举所有u的临边(u，v),对（u，v）进行松弛操作，即若，则改进，pred（v)=u。转2。复杂度:1.6.2.2. 所有顶点对间最短路 Allpairs shortest paths1.6.2.2.1. 基本算法 Basic algorithms1.6.2.2.1.1. FloydWarshall本质就是用迭代法（动态规划）:表示u到v的不经过k,k+1，n结点(除u,v外)时，从u,v的最短路长。下面用归纳法证明：k=1显然成立。假设对k成立,下面考虑k+1的情况；从u到v 且不通过k+1,， n 节点的最短路有两种可能:(1)不经过k节点,即为;(2)经过k节点，即为。由于第k+1次迭代过程中,不会影响k次的迭代结果,d用的空间即可。二维数组，记录u到v，最后经过哪个k的迭代。算法：1. k=1，对于所有u,v ,2. k=k+1，对于所有u，v,若，则，。若发现某个节点u使得， 则说明网络本来就含有负有向圈,结束。3. 若k=n，结束；否则转2.算法复杂度：1.6.2.2.1.2. Johnson本算法适用于稀疏图。它是Dijkstra和Bellman-Ford算法的综合应用。本算法用了权值改造（reweighting）技术。若图的权值非负,则对于每个结点用一次Dijkstra算法，就可以求出所有顶点对间最短路.若图中有负权，但没有负圈，则可以把权值W改造成W，W非负,使得能够使用Dijkstra算法。算法：1. 给图G，加一个新结点。对用Bellman-Ford,若有负圈，则结束；否则可以得到,即到的最短路长.O(nm）2. 对于所有边，权值改造，即令。O（m）3. 对于每个结点，用一次以Fibonacci Heap为优先队列的Dijkstra算法，可求出与其他顶点的最短路。O（nlogn+m）*O(n） 算法总复杂度。权值改造满足两个原则：（1）W 非负；（2)对于任意顶点u, v,p是在W上的u到v的最短路当且仅当p是在W上的u到v的最短路.下证，满足以上两个原则:（1）由于h是v0到v的最短路长，所以.（2）令路径,则只与以及首尾的标号h有关，不影响的决策。所以是最短路长当且仅当是最短路长,且不影响最短路p。参考文献：1 25。3 Johnsons algorithm for sparse graphs,Introduction to Algorithms,MIT Press1.6.3. 网络流 Flow network1.6.3.1. 最大流 Maximum flow在有向无权图G（V,E，C)中,其中C为每条边的容量（capability），再给每条边赋予一个流值（flow），并规定源s和汇t。最大流问题的数学模型描述如下：其中(2)，为容量限制条件：边的流量不超过边上的容量。其中（3）规定反向边的流量为正向边的流量的相反数。其中（4）可以改写成：称为流量平衡条件.它表示除了源s和汇t外的结点流入等于流出。其中(1)表示要求从源流出的流量要最大。最小切割最大流定理：s-t 最大流流值=st最小切割容量。习题：Ural 1277 Cops and Thieves (最小切割最大流）1.6.3.1.1. 基本算法 Basic algorithms1.6.3.1.1.1. Ford-Fulkerson method增广轨定理：1.6.3.1.1.1.1. EdmondsKarp al