《算法导论（原书第3版）》读书笔记

算法导论-第六部分 图算法-读书笔记
第二十一章 用于不相交集合的数据结构
第二十一章本来是第五部分里的，但它的内容和第六部分关系更为密切，所以放到了这里。

21.1 不相交集合的操作
不相交集合数据结构(disjoint-set data structure)：维护了一个不相交可变集的集合 S={S1, S2, …, Sk}，S1…Sk 都是不相交的。

在不相交可变集合中，我们选出一个元素代表这个集合，用来在判断集合是否相交时做判断用，这个元素叫做：代表（representative）。例如：x、y、z 在一个集合里，z 是这个集合的代表，在判断 x 和 y 是否相交时，看看 x 和 y 的代表是不是相同，因为他们的代表都是 z，所以它们是相交的。

MAKE-SET(X)：建立一个新的集合，它的唯一成员（因而是代表）是 x。因为各个集合不是相交的，故 x 不会出现在别的某个集合中。
UNION(X, Y)：将包含 x 和 y 的两个动态集合（表示为 Sx 和 Sy)合并成一个新的集合，即这两个集合的并集。
FIND-SET(X)：返回一个指针，这个指针指向包含 x 的（唯一）集合的代表。（返回代表来判断两个元素是否是相交的）
不相交集合数据结构的一个应用
不相交集合数据结构的许多应用之一是，确定无向图的连通分量。例如，下图包含了 4 个连通分量的图。
代码中，图 G 的顶点用 G.V 表示，边集用 G.E 表示。


21.2 不相交集合的链表表示
下图给出了实现不相交数据结构的简单方法：每个集合用一个链表来表示。

每个集合对象包含 head 和 tail 属性，head 指向第一个对象，tail 指向链表的最后一个对象。
链表中每个对象都包含 3 个属性：
一个集合成员（就是关键字的意思）
一个指向下一个对象的指针
一个指回集合对象的指针


关于合并的一个简单实现
UNION 操作比 MAKE-SET 或 FIND-SET 花的时间多。因为就像上面的图一样，在 UNION(x, y)时是把 y 加到 x 里面，除了修改 tail 指针和 x 里最后一个元素的指针，还要修改 y 里所有元素的指向集合的指针。

如果我们要把 n 个对象，创建集合并进行 UNION 操作的话，最慢的方法需要 O(n2)O(n2)时间。
如下图所示，创建时候，更新对象数为1。但在 UNION 时候，更新对象数是线性增长的（1…n-1），因为每次进行 UNION 时候，都是把大的集合向小的集合进行合并，这样要修改大的集合的每个元素的指针（是指向集合的那个指针）。这样每个操作平均需要 Θ(n)Θ(n) 时间，也就是说，一个操作的摊还时间为 Θ(n)Θ(n) 。

如果是把小的集合向大的集合上合并的话，就会快很多，这也是下面要讲的加权合并。


一种加权合并的启发式策略
把较短的表拼接到较长的表中，叫做加权合并启发策略。

21.3 不相交集合森林
在一个不相交集合森林中，每个成员仅指向它的父结点。每棵树的根包含集合的代表，并且是其自己的父结点。正如我们将要看到的那样，虽然使用这种表示的直接算法并不比使用链表表示的算法快，但通过引入两种启发式策略（按秩合并 和 路径压缩），我们能得到一个渐近最优的不相交集合数据结构。


改进运行时间的启发式策略
按秩合并(union by rank)
它类似于链表表示中使用的加权合并启发式策略。显而易见的做法是，使具有较少结点的树的根指向具有较多结点的树的根。这里并不显式地记录每个结点为根的子树的大小，而是采用一种易于分析的方法。对于每个结点，维护一个秩，它表示该结点的高度的一个上界。在使用按秩合并策略的 UNION 操作中，我们可以让具有较小秩的根指向具有较大秩的根。

路径压缩
在 FIND-SET 操作中，使用这种策略可以使查找路径中的每个结点直接指向根。路径压缩并不改变任何结点的秩。


伪代码实现
下面的伪代码使用了上面两种启发式策略：

UNION：使用了“按秩合并”策略
FIND-SET：使用了“压缩路径”
FIND-SET代码如下：

这个代码很有意思，分成两个部分分析：

递归到根结点：这个过程是找到根结点
找到根结点后的返回：最终结果，是把根结点返回给 FIND-SET 调用都。但这个过程中，把经过的所有结点的 p 指针都指向了根结点（x.p = FIND-SET(x.p)）。
UNION 和 MAKE-SET 代码如下：





union 操作会形成一棵线性树，Find 操作会把这棵线树变平

启发式策略对运行时间的影响
如果单独使用按秩合并或路径压缩，他们每一个都能发病不相交森林上操作的运行时间，而一起使用这两种启动式策略时，这种改善更大。具体时间复杂度省略。

第二十二章 基本图算法
本章主要讲”图的表示”和”图的搜索”。

1，什么是图的搜索？
是系统化地跟随图中的边，来访问图中的每个结点。

2，关于图算法
许多的图算法在一开始都会先通过搜索来获得图的结构，其它的一图算法则是对基本的搜索加以优。图搜索技巧是图算法领域的核心。

22.1 图的表示
图的表示有两种方式：

邻接链表：在表示稀疏图（边的条数 |E| 远远小于 |V|2|V|2 的图）时里非常紧凑而成为通常的选择。
邻接矩阵：在稠密图（|E| 接近 |V|2|V|2 的图）情况下，我们可能倾向于使用邻接矩阵表示法。另外，需要快速判断任意两个结点之间是否有边相连，可能也需要使用邻接矩阵表示法（ O(1) 就可以计算出来，链表法的话，需要遍历链表中每个结点）。
下看面的图就知道了，当 |E| 远远小于 |V|2|V|2 时，矩阵里的大部分都是 0，占用了很多空间但表示出有意义的内容（也就是1）非常少。这种情况下，把是 1 的部分使用链表来保存，里非常节省空间。



下面说几个后面会用到的定义：

对于图 G=(V, E) 来说，其邻接链表表示一个包含 |V| 条链表的数组 Adj 所构成，每个结点有一条链表。对于每个结点 u∈ V，邻接链表 Adj[u] 包含所有与结点 u 之间有边相连的结点 v，即 Adj[u] 包含图 G 中所有与 u邻接的结点（或指针）。例如：上图 (a) 中的 12345 每个结点都是 Adj 数组中的一个元素，结点 1 与 2 和 5 结点相连，所以 Adj[1] 这个元素所代表链表中，有 2 和 5 两个元素。（在伪代码中，我们将数组 Adj 看成图的一个属性，用 G.Adj[u] 这样的表示。）
如果 G 是一个“有向图”，则对于边 (u, v) 来说，结点 v 将出现在链表 Adj[u] 里。因此，所有邻接链表的长度之和等于 |E|。如果 G 是一个无向图，对于边 (u, v) 来说，结点 v 将出现在链表 Adj[u]里，结点 u 也将出现在链表 Adj[v] 里，因此所有邻接链表的长度之和等于 2*|E|。

有向图的边 (u, v) 表示，从顶点 u 指向 顶点 v)

无论是有向图还是无向图，邻接链表表示法的存储空间需要均为 Θ(V+E)Θ(V+E)，这正是我们所希望的数量级。

对邻接链表稍加修改，就可以用来表示权重衅。权重图是图中每条边都带有一个相关的权重的图。该权重值由一个 w: E -> R 的权重函数给出。例如：设 G=(V, E) 为一个权重图，其权重函数为 w，我们可以直接将边 (u, v) ∈ E 的权重值 w(u, v) 存放在结点 u的邻接链表中。邻接链表表示法的健壮性很高，可以对其进行简单修改来支持许多其它的图的变种。
邻接链表的一个潜在缺陷是：无法快速判断一条边 (u, v) 是否是图中的一条边，唯一的办法是在邻接链表 Adj[u] 里面搜索结点 v。邻接矩阵克服这个缺陷，但付出的代价是更大的存储空间（存储空间的渐近数量级更大)。

从上面的 图(c) 中可以看出，无向图的邻接矩阵是一个对称矩阵。由于在无向图中，边 (u, v) 和 (v, u) 是同一条边，无向图的邻接矩阵 A 就是自己的转置，即 A=ATA=AT。在某些应用中，可能只需要存放对角线及其以上的这部分（即半个矩阵），空间需要减少一半。
邻接矩阵也可以用来表示权重图。原来矩阵每个元素放 0 或 1，可以改成放权重值或函数。当不存在时，可以使用 NIL。但对于许多问题来说，可以用 0 或 无穷大 来表示可能更方便。
虽然邻接链表和邻接矩阵在渐近意义下至少是一样空间有效的，但邻接矩阵表示法更为简单，因此在图规模比较小时，倾向于使用邻接矩阵表示法。而且对于无向图来说，邻接矩阵还有一个优势：每个记录项只需要1位的空间。
22.2 广度优先搜索
广度优先搜索是最简单的图搜索算法之一，也是许多重要的图算法的原型。Prim 的最小生成树算法 和 Dijkstra 的单源最短路径算法 都使用了类似广度优先搜索的思想。

1，什么是广度优先搜索
给定图 G=(V, E) 和一个结点 s，通过对图 G中的“边”进行探索，可以发现从结点 s 到达所有结点路径。
在搜索时，先对结点 s 能到达的所有“邻接链表中的结点”（就是结点 s 链表里的结点)进行操作，再对邻接链表中的结点能够到达的结点再进行操作。。。例如，下图中，先结 s 结点的邻接链表中的结点“w, r”进行操作，然后再对结点“t, w”（w的邻接链表中的结点） 和 结点“v”（r的邻接链表中的结点)进行操作。。。

该算法能够计算从结点 s 到每个可到达的结点的距离（最小的边数)，同时生成一棵“广度优先搜索树”。该树以结点 s 为根结点，包含所有可以从 s 到达的结点。对于每个从结点 s 可以到达的结点 v，搜索树里的从 s 到 v 的简单路径，就是图 G 中从 s 到 v 的“最短路径”。这就是树的作用。该算法可用于“有向图”和“无向图”。



2，具体算法内容
在搜索时，先对结点 s 能到达的所有“邻接链表中的结点”（就是结点 s 链表里的结点)进行操作，再对邻接链表中的结点能够到达的结点再进行操作。。。例如，下图中，先结 s 结点的邻接链表中的结点“w, r”进行操作，然后再对结点“t, w”（w的邻接链表中的结点） 和 结点“v”（r的邻接链表中的结点)进行操作。。。

在搜索过程中，结点可以有3种颜色“白，灰，黑”。最开始所有结点都是白色；在搜索过程中，结点第一次被找到，结点变成灰色。当一个结点的邻接链表中的结点都被找到（也就是变成灰色)后，这个结点变成黑色。例如，上图中，最开始找的是提供出来的结点 s，s 被找到后变成灰色。色后找 s 的邻接链表中的结点 w、r，被找到后 w、r 变成灰色，s 变成黑色。。。当一个灰色结点或黑色结点被重复找到后，颜色不变。

程序如下：

注意：

队列 Q 是一个普通的先进先出的队列
Q里包含的都是灰色的结点
3，分析
总运行时间为 O(V+E)

4，广度优先树
下面的伪代码将打印出从结点 s 到 v 的一条最短路径上的所有结点，这里假定 BFS 已经计算出一棵广度优先树。

程序有点像二叉树搜索的程序，先递归找到结点 s，再在回去路上打印出所有结点。


22.3 深度优先搜索
深度优先搜索总是对最近才发现的结点 v 的出发边进行探索，直到该结点的所有出发边都被发现为止。一旦结点 v 的所有出发边都被发现，搜索则“回溯”到 v 的前驱结点（v 是经过该结点才被找到的)，来搜索该前驱结点的出发边。一直到最开始结点可以到达的所有结点都被找到。如果还有没有被找到的结点，则从没有被找到的结点中随便找一个，再进行同样的搜索。直到所有结点都被找到为止。

在讨论广度优先搜索算法时，我们将源结点（最开始的那个结点)的数量限制为一个，而深度优先搜索则可以有多个源结点。虽然从概念上看，广度优先搜索可以从多个源结点开始搜索，深度优先搜索也可以限制为从一个源结点开始，但本书所采取的方法所反映的是这些搜索结果是如何被使用的。广度优先搜索通常用来寻找从特定源结点出发的最短路径距离（及其相关的前驱子图），而深度优先搜索则沉淀作为另一个算法里的一个子程序，我们将在本章后面看到这点。

每当发现一个结点 v 时，深度优先搜索算法将这个事件进行记录，将 v 的前驱属性 x.π 设置为 u。不过与广度优先不同的是，广度优先搜索的前驱子图形成一棵树，而深度优先搜索的前驱子图可能由多棵树组成，因为搜索可能从多个源结点重复进行。例如，下面的图中，需要从 u 和 w 两个源结点进行搜索，才能搜索到所有的结点，这样就会有两棵树，而前驱子树也会有两棵。

深度优先搜索中，结点也是有颜色的，意义和广度优先一样。这样的方法可以保证每个结点仅在一棵尝试优先树中发现。因此，所有尝试优先树是不相交的。

尝试优先算法还在每个结点上加一个时间戳。每个结点有两个时间戳：

第一个时间戳 v.d 记录 v 第一次被找到的时间（涂上灰色的时候)
第二个时间戳 v.f 记录的是“v 的邻接链表都扫描完成”的时间
结点 u 在时刻 u.d 之前为白色，在时间 u.d 和 u.f 之间为灰色，在时间 u.f 之后为黑色。

图如下：


程序如下：


注意：

time 是一个全局变量
深度优先算法的结果，可能依赖于下面两点：（不过这些不同的访问次序在实际中不会导致问题，因为我们沉勇可以对任意的深度优先搜索结果加以有效的利用，并获得等价的结果)
算法 DFS 第5行对结点进行检查的顺序
算法 DFS-VISIT 第4行对一个结点的邻接结点进行访问的次序
分析
深度优先搜索的运行时间为：Θ(V+E)Θ(V+E)
深度优先搜索的性质
1，其生成的前驱子图 Gπ 形成一个由多棵树所构成的森林，这是因为深度优先树的结构与 DFS-VISIT 的递归调用结构完全对应。

什么是前驱子图？个人理解的意思就是，生成的树。广度优先生成一棵，深度优先成生多棵。

2，结点的发现时间和完成时间具有所谓的括号化结构（parenthesis structure）。如果以左括号 (u 来表示结点 u 的发现，以右括号 u) 来表示结点 u 的完成，则发现和完成的历史记录会形成一个规整的表达式，即所有括号都适当地嵌套在一起。如下图 (b)


边的分类
深度优先搜索的另一个有趣的性质是，可以通过搜索来对输入图 G=(V, E) 的边进行分类。每条边的类型可以提供关于图的重要信息。例如，下一节我们将看到有向图是无环图，当且仅当深度优先搜索不产生“后向”边。

树边：是深度优先森林 Gπ 中的边。如果结点 v 是因为算法对边 (u, v) 的探索而首先被发现的，则 (u, v) 是一条树边。

后向边：是对于 边 (u, v) 来说，将结点 u 连接到其所在的深度优先树中的一个祖先结点 v 的边。简单来说，v 是 u 的一直向上的祖先结点。如果 v 是 u 的祖先结点的其它子结点，就算 v 比 u 高，也不是后向边，那是横向边。自循环的边也被认识是后向边。

例如，x 到 z 是后向边。但假设如果 x 到 w 也有一条线的话，这条边不是后向边，是横向边。

前向边：是将结点 u 连接到其所在的深度优先树中一个后代结点 v 的边 (u, v)。如果后台结点 v 是一真向下的后代结点的兄弟结点的话，那不是前向边，是横向边。

例如，s 到 w 是前向边。但 w 到 x 不是前向边。

横向边：指其他所有的边。这些边可以连接同一棵深度优先树中的结点，只要其中一个结点不是另一个结点的祖先，也可以连接不同深度优先树中的两个结点。

例如。v 到 s/w 都是横向边。u 到 v 是横向边。

遇到某些边时，DFS有足够的信息来对这些边进行分类。这里的关键是，当第一次探索边 (u, v) 时，结点 v 的颜色能够告诉我们关于该条边的一些信息。

结点 v 为白色时，表明 边(u, v) 是一条树边。
结点 v 为灰色时，表明 边(u, v) 是一条后向边。
结点 v 为黑色时，表明 边(u, v) 是一条前向边 或 横向边。
这些信息，看一些图的变化过程就能看出来。

第二十三章 最小生成树
在电子电路设计中，我们沉淀老板娘多个组件的针脚连在一起。要连接 n 个针脚，我们可以使用 n-1 根连线，每根连线连接两个针脚。但我们希望使用的连线长度最短的那种方法。

上述布线问题，可以用一个连通无向图 G=(V, E) 来表示。这里

V 是针脚的集合
E 是针脚之间的可能连接
并且对于每条边 (u, v) ∈ E
权重 w(u, v) 作为链接针脚 u 和 v 的代价（也就是连线长度）
我们希望得取一个无环子集 T ⊆ E，既能够把所有的针脚连接起来，又具有最小权重，即 w(T)=∑(u,v)∈Tw(u,v)w(T)=∑(u,v)∈Tw(u,v)。由于 T 是无环的，并且连通所有的结点，因此 T 必须是一棵树。我们称这样的树为(图G的)生成树。因为它是由图 G 所生成的。我们称求该生成树的问题为“最小生成树问题”，如下图



关于下面要讨论的最小生成树算法

下面讨论最小生成树问题的两种算法：Kruskal 和 Prim。如果使用普通的二叉树，那么可以很容易地将两个算法的时间复杂度限制在 O(ElgV) 的数量级内。但如果使用斐波那契堆，Prim算法的运行时间将改善为 O(E + VlgV)。此运行时间在 |V| 远远 小于 |E| 的情况下较二叉堆有很大改进（也就是“结点数”远远小于“边数”）。

普通情况下的 Kruskal 和 Prim 时间复杂度：O(ElgV)
|V| 远远 小于 |E| 并且 使用 Prim 算法的时间复杂度：O(E + VlgV)
第二种的时间复杂度上，因为|V| 远远 小于 |E|，所以 VlgV 也远远小于 ElgV。

这两种算法都是贪心算法。

23.1 最小生成树的形成
我们先把前提条件说一下：

假设有一个连通无向图 G=(V, E) 和权重函数 w: E->R （这个函数个人理解是 w(E)=R 这个意思，R 是函数的值）

我们希望找出图 G 的一棵最小生成树。

本章的两个算法都使用贪心策略来解决问题，方式不同，但可以使用下面的通过方法来表示大概。



A 是某棵最小生成树的一个子集。每一步我们要做的事情是选择一条边 (u, v)，将其加到集合 A 中，使得 A 不违反循环不变式，即 A 并 {(u, v)} 也是某棵最小生成树的子集。由于我们可以安全地将这种边加入到集合 A 而不会破坏 A 的循环不变式，因此称这样的边为集合 A 的安全边。

上面代码中，第3行是关键。第3行是要找到一条安全边。循环不变式告诉我们存在一棵生成树 T ，满足 A ⊆ T。在 while 体内，集合 A 一定是 T 的真子集，因此必然存在一条边 (u, v) ∈ T，使得 (u, v) ∉ A，并且 (u, v) 对于集合 A 是安全的。

关于一些定义
切割：一个切割就是一个条用于划分两部分的线。例如：切割(S, V-S) 是把结点分成两部分，一部分结点集合是 S，另一部分就是 V-S（也就是结点总集合 V 减去 刚才的结点集合 S）。可以看图 (a)
横跨切割：如果一条边 (u, v) 属于 E 的一个端点位于集合 S，另一个端点位于集合 V-S，则称该条边横跨切割(S, V-S)。
Respect：如果集合 A 中不存在横跨该切割的边，则称该切割 respect 集合A。这里 respect 感觉应该翻译成“分隔”的意思。因为集合A 没有任何边和“切割”相交，那么它就被分隔在“切割”的一面了。
轻量级边：横跨切割(S, V-S) 的所有边中，权重最小的边称为“轻量级边”。注意，轻量级边并不是唯一的。如果一条边是满足某个性质的所有边中权重最小的，则称该条边是满足给定性质的一条轻量级边。
感觉“切割”如果翻译成“切割线”更好一些。



23.2 Kruskal 和 Prim 算法
本节对两个经典算法进行讨论。每种算法都是一条具体的规则来确定 GENERIC-MST 算法第 3 行所描述的安全边。

在 Kruskal 算法中，集合A 是一个森林，其结点就是给定图的结点。每次加入到集合A 中的安全边永远是权重最小的连接两个不同部分的边。
在 Prim 算法中，集合A 则一棵树。每次加入到 A 中的安全边就远是连接 A 和 A 之外的某个结点的的边中权重最小的边。
Kruskal 算法
主要思想就是，取最小权重的边，然后进行合并。具体内容如下：

先把每条边按权重进行升序排序
然后对排完序每条边进行迭代
如果当前这条边的两个结点不是在同一棵树里，就把“两个结点所表示的树”进行合并，再加到返回集合中
因为每次取的边都是“剩下边中”权重最小的边，所以属于贪心算法。

Kruskal 算法的实现与 21.1 节所讨论的计算连通分量的算法类似。我们使用一个不相交集合数据结构来维护几个互不相交的元素集合。每个集合代表当前森林中的一棵树。

使用FIND-SET(u) 用来返回包含元素 u 的集合的代表元素。我们可以通过测试 FIND-SET(u) 是否等于 FIND-SET(v) 来判断结点 u 和 v 是否属于同一棵树。
使用 UNION 来对两棵树进行合并。




Prim 算法
主要思想：

从所有结点中，任意选择一个结点 r 。
结点 r 连接的所有结点的边中，选择一个权重最小的边，加入到 r 所在的集合。
一直到所有结点都被加进来为止。


程序如下：



关于程序还有一些要解释的：

这个程序是使用“父指针”的方式，把所有结点连成了一棵树。并不是像 Kruskal 程序一样，用一个集合来保存所有的边。
v.key 保存的是“和 v 连接的边”的权重。例如：结点b 和 a、c、h 连接，所有它有 3 个权重可以选择 a-4、c-7、h-11。b.key 里应该保存 4，但因为最开始的结点的不确定性，所以可能最开始保存的不是 4，而是其它的权重，但最后终于保存最小权重。
迭代方式，是使用最小堆的方式。
首先把所有的元素都放到堆里，以元素的 key 属性作为堆的比较值。在放到堆里时，把任意指定的结点的 key 属性设置成 0，其它结点设置成无穷大，这样在从最小堆里取得最小元素时，就会把这个“任意指定”的结点第一个取出来处理。（程序1~4行是设置 key 的地方）
然后在再从堆里取得最小结点 u，然后把结点 u 的链表中的结点 v 每个都取出来，进行设置：如果 v 还在 堆中 并且 w(u, v) < v.key（u和v 的权重 < v 现在的权重），就设置 v 的父结点 和 key 的值。（设置完后，v 可能还在堆里，这样下次取得堆里最小 key的结点时候，就可能把它取出来）
循环上一步，直到堆里所有的元素都处理完毕，变成堆里没有任何元素。
关于在判断 v 是否在还在堆中的问题，由于堆一般没有“查找”方法，所以这个判断是由一个标志位来做的。在从堆中删除结点的时候，设置该标志位。
在第7行取得堆中最小元素时，就是取得某条横跨“切割(V-Q, Q)”的轻量级边的一个端点。因为在最开始时，所有的结点都在堆Q 中，所以 (V-Q, Q) = (0, Q)。从堆Q 中取得一个元素后，切割(V-Q, Q) 就在新取出的结点u 和其它结点中间了，这样 u 连接哪个结点，都是横跨切割的。（至少看到这，没看到切割和横跨切割的概念对我们有什么作用。。。）
Prim 算法的运行时间取决于最小堆Q的实现方式。

如果将 Q 实现为一个二叉最小堆：

可以使用 BUILD-MIN-HEAP 来执行算法的第15行，时间成本为 O(V)。while 循环中的语句一共要执行 |V| 次，由于每个 EXTRACT-MIN 操作需要的时间成本为 O(lgV)，所以 EXTRACT-MIN 操作需要的总共时间成本为 O(VlgV)。
所有邻接链表长度之和为 2|E|，算法811行的 for 循环的总执行次数为 O(E)。在 for 循环里面，可以使用常数时间判断”一个结点是否属于Q“
第11行的赋值操作，还隐含 DECREASE-KEY 操作（因为需要把修改后的的 key 和 π 保存到结点上），该操作在二叉最小堆上的执行时间为 O(lgV)。因此 Prim 算法总时间为：O(VlgV + ElgV) = O(ElgV)。从渐近意义上来说，它与 Kruskal 的运行时间相同。
如果使用斐波那契堆来实现最小优先堆Q，Prim 算法的渐近运行时间可以得到进一步改善：

EXTRACT-MIN 操作时间的摊还代价为 O(lgV)（最小堆的时间为O(VlgV)，少个倍数V），而 DESCRASE-KEY 操作的摊还时间为 O(1)（最小堆的时间为O(lgV)）。
使用斐波那契堆实现最小堆的话，时间复杂度改善为 O(E + VlgV)
参考：

Prim 算法（1）
​
todo：

看一下那个最容易明白的博客上的最小生成树文章。
为什么所有邻接链表长度之和为 2|E|
为什么斐波那契堆的 DESCRASE-KEY 的摊还时间为 O(1)

第二十四章 单源最短路径
Patrick 教授希望找到一条从菲尼克斯到印第安纳波利斯的最短路径，如何才能找出这样一条最短路径呢？

一种可能的办法是，先将从菲尼克斯到印第安纳波利斯的所有路径都找出来，将每条路径上的距离都累加起来，然后选择一条最短路径。但是即使在不允许环路的情况下，也需要检查无数种可能的路径，其中大部分都不值得检查。例如，一条从菲尼克斯经过西雅图再到印第安纳波利斯的路径显然不符合要求，因为西雅图已经偏离了目标方向好几英里。

本章及第25章将阐述，如何高效地解决这个问题。在最短路径问题中，我们给定一个带权重的有向图 G=(V, E) 和权重函数 w:E->R，该权重函数将每条边映射到实数值的权重上。图中一条路径 p=(v0, v1, …, vk) 的权重 w(p) 是构成该路径的所有边的权重之和：

w(p)=∑ki=1w(vi−1,vi)w(p)=∑i=1kw(vi−1,vi)
这个公式就是 w(v0,v1) + w(v1,v2) + … + w(vk-1,vk) 的和。

定义从结点 u 到 v 的最短路径权重 δ(u,v)δ(u,v) 如下：



在求菲尼克斯到印第安纳波利斯的最短路径的例子中，我们可以用一幅图来表示道路的交通图：结点代表城市，边代表城市之间的道路，边上的权重代表道路的长度。我们的目标就是找出一条给定城市菲尼克斯到印第安纳波利斯的最短路径。（当然权重也可以代表非距离度量单位，如：时间，成本，罚款，损失或其它）

為了解決較為廣義的情境，接下來討論的最短路徑問題將考慮的是一個带权重的有向图，以权重总和表示路径成本，並以具有方向性的边表示两个结点之间的关系。

无向图的問題能夠以有向图的模型解決，反之則無法。
不具权重的边也能夠以带权重的边模拟(将全部权重设置成相同值即可)，反之則無法。
可以視為只能處理无权重图的“广度优先”和“深度优先”的扩充包。（不有理解什么意思）
最短路径的几个变体
单源最短路径问题：这是我们集中精力讨论的问题。简单地说，就是找出从一个源结点 s 到图中各个结点 v 的最短路径。单源最短路径问题可以用来解决许多其他问题，其中就包括下面的几个最短路径问题。
单目的地最短路径问题：找到从每个结点 v 到“给定目的地”结点 t 的最短路径。如果将图的每条边的方向翻转过来，我们就可以将这个问题转换为单源最短路径问题。是单源最短路径问题的变种。
单结点对最短路径问题：找到从给定结点 u 到 v 的最短路径。如果解决了针对单个结点 u 的单源最短路径问题，那么也就解了这个问题。而且，在该问题的所有已知算法中，最坏情况下的渐近运行时间都和最好的单源最短路径算法的运行时间一样。是单源最短路径问题子问题。
所有结点对最短路径问题：对于每对结点 u 和 v，找到从结点 u 到 v 的最短路径。虽然可以针对每个结点运行一回单源最短路径算法，但通常可以更快地解决这个问题。此外，该问题结构的本身就很有趣。第25章将详细讨论所有的结点对最短路径问题。
最短路径的最优子结构
最短路径算法通常依赖最短路径的一个重要性质：两个结点之间的一条最短路径包含着其它的最短路径。最优子结点是可以使用动态规划和贪心算法的一个重要指标。我们将在24.3文件读的 Dijkstra 算法就是一个贪心算法，而 Floyd-Warshall 算法则是一个动态规划算法，该算法能够找出所有结点对之间的最短路径。

负权重的边
如果图G 包含从结点s 可以达到的权重为负值的环路，而最短路径权重无定义。从 s 到该一路上的任意结点的路径，都不可能是最短路径，因为我们只要沿着任何“最短”路径再遍历一次权重为负值的环路，则总是可以找一条权重更小的路径。如果从结点s 到 v 的某条路径上存在权重为负值的环路，我们定义 δ(s,v)δ(s,v)=负无穷大



某些最短路径算法（如：Dijkstra算法）假设输入图的所有边的权重为非负值。例如：道路交通图的例子中，所有的权重都为正值。另外一些算法（如：Bellman-Ford算法），允许输入图中包含负权重的边。只要没有可以从源结点到达的“权重为负值的环路”，就可以生成正确的答案。

环路
一条最短路径可以包含环路吗？正如我们已经看到的，最短路径不能包含权重为负值的环路。而事实上，最短路径也不能包含权重为正值的环路，因为只要将环路从路径上删除就可以得到一条源结点和终结点相同的一条权重更小的路径。

当环路的权重为0时，我们可以从任何路径上删除权重为 0 的环路而得到另一条权重相同的路径。因此，如果从 s 到 v 存在一条包含权重为 0 的环路最短路径，则也同时存在一条不包含该环路的的“从 s 到 v 的最短路径”。只要一条最短路径上还有权重为 0 的环路，我们就可以重复删除这些环路，直到得到一条不包括环路的最短路径。因此，我们可以假定在找到的最短路径中没有环路，即他们都是简单路径。由于图G=(V, E)中任意无环路径最多包含 |V| 个不同的结点，它也最多包含 |V|-1 条边。因此，我们可以将注意力集中到最多只包含 |V|-1 条边的最短路径上。

总结一下：

一个最短路径，如果包含权重为正值 并且 不等于0 的环路，那个最短路径不可能是最短路径。减去环路后，才是最短路径。
一个最短路径，如果包含权重为正值 并且 等于0 的环路，可以删除环路而得到另一条最短路径，所以还是去掉环路计算比较好。
总而言之：还是需要去掉环路，才得到最短路径。

最短路径的表示
最短路径的表示与广度优先搜索树的表示类似，对于每个结点 v，我们维护一个前驱结点 v.π。该前驱结点可能是另一个结点或者NIL。本章是最短路径算法将对每个结点的 π 属性进行设置，这样将从结点 v 开始的前驱结点链反转过来，就是从 s 到 v 的一条最短路径。22.2 节中的程序 PRINT-PATH(G, s, v) 打印出的就是结点 s 到 v 的一条最短路径。

注意，但在运行最短路径算法的过程中，π 值并不一定能给出最短路径，只有在程序运行终了时，才能给出。下面给出一些定义，为了以后学习方便先写出来：

在这里，我们定义结点集 VπVπ 为图G 中前驱结点不为 NIL 的结点的集合，再加上源结点 s，即：

Vπ={v∈V:v.π≠NIL}∪{s}Vπ={v∈V:v.π≠NIL}∪{s}
注意：是 VπVπ 不为 NIL 的结点的集合，也就是形成树后，树上的所有结点。

有向边集合 EπEπ 是由 VπVπ 的结点 π 值所诱导的边的集合，即：

Eπ={(v.π,v)∈E:v∈Vπ−{s}}Eπ={(v.π,v)∈E:v∈Vπ−{s}}
注意：EπEπ 就是树上的所有结点，形成的边。

我们将证明本章的算法所生成的 π 值具有以下性质：在算法终止时， GπGπ 是一棵“最短路径树”。也可以说，最短路径树是一棵有根结点的树，该树包括了从源结点 s 到“每个可以从 s 到达的结点”的一条最短路径。一棵最短路径树有点类似于 22.2 节中的广度优先树，但它所包括的最短路径是以边的权重来定义的，而不是边的条数。更粝我地说，设 G=(V, E) 是一条带权重的有向图，其权重函数为 w:E->R，假定 G 不包含 s 可以不能包含的权重为负值的环路，因此所有最短路径都有定义。一棵根结点为 s 的最短路径树是一个有向子图 G’=(V’, E’)，这里 V’ ⊆ V，E’ ⊆ E，满足：

V’ 是图G 中从源结点 s 可以到达的所有结点的集合
G’ 形成一棵根结点为 s 的树
对于所有结点 v ∈ V’，图G’ 中从结点 s 到 v 的唯一简单路径就是图G 中从结点 s 到 v 的一条最短路径。
要指出，最短路径不一定是唯一的，最短路径树也不一定是唯一的。



松弛操作
重要：本章的每个算法都是将调用 INITIALIZE-SINGLE-SOURCE 方法，然后重复对边进行松弛。而且松弛也是唯一导致“最短路径估计”和“前驱结点”发生变化的操作。本章所讨论的所有算法之间的不同之处是：对每条边进行松弛的次数和松弛边的次序不同。Dijkstra 算法和用于有向无环图的最短路径算法对每条边仅松弛一次。Bellman-Ford 算法则对每条边松弛 |V|-1 次。

对于每个结点 v 来说，我们维持一个发生 v.d，用来记录从源结点 s 到结点 v 的最短路径权重的上界，我们称 v.d 为 s 到 v 的最短路径估计。（注意，是上界，因为无法一次把准确的最短路径权重计算出来。程序运算完还是能计算出来的）

对最短路径估计和前驱结点初始化程序，我们用下面的 Θ(V)Θ(V) 程序来做这个操作：



注意，该程序执行完后，会有以下属性，在理解更下面的程序时，要留意这些条件：

对于结点 v ∈ V，我们有 v.π=NIL，s.d=0
对于所有结点 v ∈ V-{s}，我们有 v.d=无穷大
对一条边 (u, v) 的松弛过程为：

先测试一下是否可以对从 s 到 v 的最短路径进行改善。测试方法是，将从结点 s 到 u 之间的最短路径距离，加上结点 u 与v 之间的边权重，并与当前的 s 到 v 的“最短路径估计”进行比较。如果前者更小，则对 v.d 和 v.π 进行更新。松弛操作可能降低最短路径的估计值 v.d 并更新 v 的前驱属性 v.π。




其它性质
从上面的图上来看，松弛操作并不复杂。在形成最短路径时，有的算法可能只是通过一系列的松弛操作，就可以计算出来。下面是一些性质，不详细说明：

三角不等式性质
上界性质
收敛性质
路径松弛性质
前驱子图性质
性质的具体意义，请参考：Shortest Path：Intro(簡介)，非常容易理解

24.1 Bellman-Ford 算法
Bellman-Ford 算法解决：一般情况下的单源最短路径问题，而且边的权重可以为负值（很多场合都可以使用，但别的算法的话，可能只能工作在特定的场合）。

算法的定义如下：

带有权重的有向图 G=(V, E) 和权重函数 w:E->R
返回值是一个布尔值，以表明是否存在一个从源结点可以到达的“权重为负值的环路”。如果存在这样的环路，就不存在解决方案。
Bellman-Ford 算法通过对边进行“松弛操作”来渐近地降低从源结点 s 到 每个结点 v 的最短路径的估计值 v.d，直到估计值与实际的最短路径权重 δ(s, v) 相同为止。返回 TRUE 的话，表示可以找到解决方案（即：不包含从可以源结点到达权重为负值的环路）




上较中的 b~e 应该是 |V|-1 次循环中的一次循环的结果。这个例子的不太好，执行 |V|-1 次循环一定可以取得最小路径，但一次循环都取得了最小路径。

关于是否有解决方案的判断，根据上面的其它性质中的“三角不等式性质”，全都松弛完的边必然：δ(S,Y) ≤ δ(S,X) + w(X,Y)。如果有 δ(S,Y) > δ(S,X) + w(X,Y) 的话，说明出现了权重为负值的环路。

为什么这么做会有效？

根據路径松弛性质，考慮一條從vertex(0)到vertex(K)之路徑 P: v0 − v1 − … − vk，如果在對path 之 edge 進行松弛的順序中，曾經出現edge(v0,v1)、edge(v1,v2)、…、edge(vK-1,vK)的順序，那麼這條path一定是最短路徑，滿足distance[K]=δ(v0,vK)。

在對edge(v1,v2)進行松弛之前，只要已經對edge(v0,v1)進行過松弛，那麼，不管還有其餘哪一條edge已經進行過松弛，distance[2]必定會等於δ(0,2)，因為收敛性质。
Bellman-Ford Algorihm就用最直覺的方式滿足路径松弛性质：

一共執行|V|−1次循环。
在每一次循环裡，對「所有的edge」進行松弛。
经过|V|−1次的「所有edge之松弛」後，必定能夠產生「按照最短路徑上之edge順序的松弛順序」，也就能夠得到最短路徑。由於從起點走到任一vertex之最短路徑，最多只會有|V|−1條edge，因此，執行|V|−1次循环必定能夠滿足「最壞情況」(worst case)。
时间复杂度
O(VE)

第1行的初始化操作需要时间为 Θ(V)Θ(V)，第24行循环运行时间为 Θ(E)Θ(E)，且一共要进行 |V|-1 次循环，第57行的 for 循环所需时间为 O(E)。Θ(V+EV+E)Θ(V+EV+E) = O(VE)

24.2 有向无环图中的单源最短路径问题
如果根据结点的拓扑排序次序来对“带权重的”有向无环图进行边的“松弛操作”，可以在 Θ(V+E)Θ(V+E)时间内计算出单个源结点到所有结点之间最短路径。在有向无环图中，即使存在权重为负值的边，但因为没有权重为负值的环路，所以最短路径是存在的。

Bellman-Ford 算法的时间复杂度为 O(VE)。

算法先对有向无环图进行拓扑排序(参照22.4)，以确定结点之间的一个线性次序。如果有向无环图包含从结点 u 到 结点 v 的一条路径，则在拓扑排序中 u 在 v 的前面。我们只需要按照拓扑排序的次序对结点进行一遍处理即可。每次对一个结点进行处理时，我们对该结点发出的所有的边进行松弛操作。

拓扑排序方法：使用深度优先的方式，查找每棵前驱树。并且按树上的结点的时间属性，进行倒序排序。




时间复杂度
Θ(V+E)Θ(V+E)
第1行的拓扑排序时间为 Θ(V+E)Θ(V+E)，第2行对初始化方法的调用时间为Θ(V)Θ(V)，第35行的 for 循环（外循环）对于每个结点执行一遍，而第45行（内循环）对每条边刚好松弛一次。因为内循环每次的运行时间为 Θ(1)Θ(1)（这里使用了聚合分析），所在算法的运行时间为 Θ(V+E)Θ(V+E)。对于邻接链表表示的图来说，这个时间为线性级。

为什么比 Bellman-Ford 算法速度快？

Bellman-Ford：要执行 |V|-1 循环，每次循环对所有的边进行松弛。所以是 O(VE)。
有向无环图：先对所有结点进行排序（花费：O(V)），然后对所有的边进行松弛（花费：O(E)），所以是 O(V + E)。
其它
算法 DAG-SHORTEST-PATHS 的一个有趣的应用是在 PERT 图分析中，进行“关键路径”的判断。todo 再写一下

24.3 Dijkstra 算法
Dijkstra 算法也是解决“带权重”的、“有向图”上的单源最短路径问题，该算法要求权重都为非负值。

Dijkstra 算法主要思想是：

从源结点 s 发出，对邻接链表节点进行松弛操作
在松弛后的结点中，找到权重最小的结点，对邻接链表节点进行松弛操作
重复上一步的操作，直到所有的结点者进行过了松弛操作。每对一个结点进行松弛操作后，就把这个结点放到集合 S 中（这个集合现在看起来只是保存做完松弛操作的结点）。



注意：

Dijkstra 算法是把未做“松弛操作”的结点中，权重最小的结点取出来，对这个结点的邻接链表中的结点做松弛操作。例如，(b) 中 y-5 比 t-10 结点的权重小，所以取出结点 y 。(d) 中 t-8 是权重最小的结点，所以取出 t 。注意一下，(c) 时 x 的父节点是 y ，但在对结点 z 做松弛操作后，是更改了 x 的父结点指针，所以 z 变在了 x 的父结点。

在算法第8行所调用的Relax操作中，会调用Decrease-Key操作，更新结点的权重值。

为什么从最小数据结构Q中取得的结点，就能肯定能找到最短路径呢？

這裡不進行嚴謹證明(證明請參考：Ashley Montanaro：Priority queues and Dijkstra’s algorithm)，只就基本條件推論。

前面提到，Dijkstra’s Algorithm的使用時機是，當Graph中的weight皆為非負實數(weight≥0weight≥0)，此時：

Graph中的所有cycle之wieght總和必定是正值(positive value)；
亦即，路徑中的edge越多，其weight總和只會增加或持平，不可能減少。
那麼再看下图，從结点(0)走到结点(5)有兩個選擇：

一個是經過edge(0,5)，成本為11；
另一個是經過edge(0,1)，再經過其他结点(例如，Path:0−1−2−3−5)，最後抵達结点(5)，由於edge(0,1)之weight已經是88，可以確定的是，經過edge(0,1)的這條path之weight總和必定大於8。
顯然，直接經過edge(0,5)會是從结点(0)走到结点(5)最短的路徑。

更廣義地說，從最小数据结点Q中挑選距离最小结点，並將其從Q中移除，必定表示，已經找到從源结点走到该结点之最短路径。


分析
Dijkstra 算法有多快？

该算法在执行中，需要三种优先数据结构操作：

Insert：算法第3行所隐含的操作。调用 |V| 次。
Extract-Min：算法第5行。调用 |V| 次。
Decrease-Key：算法第8行所调用的Relax操作中。调用 |E| 次。
该算法对每个结点调用一次 Insert 和 Extract-Min 操作。因为每个结点仅被加入到集合 S 一次，邻接链表 Adj[u] 中的每条边在整个算法运行期间也只被检查一次（在7~8行的 for 循环里）。由于所有邻接链表中的边的总数为 |E|，该 for 循环的执行次数一共为 |E|次，因此该算法调用 Decrease-Key 最多 |E|次。

所以，Dijkstra 算法的总运行时间，要看上面的三种操作的时间。上面三种操作的时间，就要看用什么方法实现优先数据结构了。

1，用队列实现

通过利用结点的编号 1~|V| 来维持最小优先数据结构。三种操作的时间为：

Insert：O(1)，放在队列尾部。
Extract-Min：O(V)，要查看所有的结点。
Decrease-Key：O(1)，按序号进行存放，所以可以立刻找到位置。
因为总时间为： O(Insert + Extract-Min + Decrease-Key) = O(V + V + E)

把队列操作时间代入：O(V + V + E) = V * O(1) + V * O(V) + E * O(1) = O(V+V2+E)O(V+V2+E) = O(V2)O(V2)
总运行时间为：O(V2)O(V2)

2，用二叉堆实现

如果是稀疏图，特别是 E=o(V2/lgV)E=o(V2/lgV)，则可以使用二叉堆来实现。

Insert：整个建堆时间为 O(V)
Extract-Min：O(lgV)
Decrease-Key：O(lgV)
因为总时间为： O(Insert + Extract-Min + Decrease-Key) = O(V + V + E)

把队列操作时间代入：O(V + V + E) = O(V) + V * O(lgV) + E * O(lgV) = O(V) + O((V + E)lgV)) = O(ElgV) （如果所有结点都可以从源结点到达）

总运行时间为：O(ElgV)（若 E=o(V2/lgV)E=o(V2/lgV) 则该时间成本相对于 O(V2)O(V2) 要小）

（todo 为什么“如果所有结点都可以从源结点到达”，时间就可以从O((V + E)lgV)) 变成O(ElgV)呢？）

3，用斐波那契堆实现

Insert：整个建堆时间为 O(V)
Extract-Min：O(lgV)
Decrease-Key：O(1)
使用斐波那契堆的动机是，人们观察到在 Dijkstra 算法中，Decrease-Key 操作通常比 Extract-Min 操作更多，所以使用斐波那契堆能够将 Decrease-Key 操作的时间降低到 o(lgV) 而又不增加 Extract-Min 操作的时间。

总运行时间为：O(VlgV + E)

最后
Dijkstra 算法既类似于广度优先算法，也有点类似于最小生成树的 Prim 算法。

它与广度优先算法的类似点在于：集合S 对应的是广度优先中的黑色结点集合。正如集合 S 中的结点的最短路径权重已经计算出来一样，在广度优先中，黑色结点的正确的广度优先距离也已经计算出来。

个人感觉和广度优先类似的地方是（Prim 算法也有相同的类似点），广度优先是对每个一个结点连接的结点进行全部计算，然后再找另一个结点，再对另一个结点所连接的结点进行计算（说连接，因为它可以是无向图）。Dijkstra 算法也是如此，先对一个结点的邻接链表里的结点进行计算（邻接链表里的结点也是当前结点通向的结点集合。说通向，因为是针对有向图），再从剩下的结点中，选出一个权重最小的，再对它的邻接链表里的结点进行计算。

它与 Prim 算法相似的地方是，两个算法都使用最小优先数据结构来寻找给定集合之外的“最小权重”结点，将该结点加入到集合里，并对集合外面的结点的权重进行相应调整。（这个地方在书中的表述，和个人理解有点不一样。但大概意思都差不多）

还有一点，Dijkstra 算法和 Prim 很像，Dijkstra 是用来处理单源最短路径的，而 Prim 是用来处理最小生成树的。Dijkstra 和 Bellman-Ford 和 DAG 是处理同一类问题。

总结
Bellman-Ford 算法、有向无环图单源最短路径算法 和 Dijkstra算法，都是解决单源最短路径问题的算法，有什么不同呢？

Bellman-Ford：

可以判断是否是有解决方案（即：判断是否包含从可以源结点到达权重为负值的环路）
权重可以为负
不可以有权重为负的环路。有权重为正的环路没有关系。
时间复杂度为：O(VE)
有向无环图：

不可以判断是否是有解决方案。
权重可以为负
不可以有环路，不管正值的还是负值的
时间复杂度为：Θ(V+E)Θ(V+E)
Dijkstra：

不可以判断是否是有解决方案。
权重不能为负
可以有环路（因为权重不能为负，所以只能有权重为正值的环路）
时间复杂度为：O(VlgV + E) (最小可能)
Bellman-Ford 、有向无环图 和 Dijkstra 的算法时间复杂度的比较
关于时间复杂度方面：

Bellman-Ford：要执行 |V|-1 循环，每次循环对所有的边进行松弛。所以是 O(VE)。
有向无环图：先对所有结点进行排序（花费：O(V)），然后对所有的边进行松弛（花费：O(E)），所以是 O(V + E)。
Dijkstra：也是对所有边进行松弛一次，具体内容为：对每个结点做后面的操作：取得邻接链表中的结点，进行松弛。因为和数据结点有关，所以使用不同的数据结构，时间复杂度也不一样：
若使用普通数组(array)，需要O(E+V2)O(E+V2)
若使用Binary Heap，需要O((E+V)lgV)
若使用Fibonacci Heap，只需要O(E+VlgV)
将以上描述做成表格，如下：

_ 有positive cycle 沒有positive cycle
有negative weight Bellman-Ford on DAG
沒有negative weight Dijkstra All three
Bellman-Ford on DAG Dijkstra(worst) Dijkstra(best)
O(VE) O(V+E) O(V2)O(V2) O(E+VlogV)

第二十五章 所有结点对的最短路径问题
要解决“所有结点对的最短路径问题”，可能通过运行 |V| 次单源最短路径算法来解决，每次使用一个不同的结点作为源结点。可使用下面几种方法：

如果所有的边的权重为非负值，还可以使用 Dijkstra 算法。如果使用数组作为数据结构的话，时间为 O(V3+VE)=O(V3)O(V3+VE)=O(V3)；如果使用二叉堆，时间为 O(VElgV)（这个时间在稀疏图的情况下，是一个较大的改进)；如果使用斐波那契堆，运行时间为 O(V2lgV+VE)O(V2lgV+VE)。
如果所有的边的权重有负值，就要使用 Bellman-Ford 算法。时间复杂度为：O(V2E)O(V2E)。稠密图的情况下，运行时间为 O(V4)O(V4)
时间复杂度推论过程如下：
上述提到的两种演算法之时间复杂度如表一：

Bellman-Ford Dijkstra(worst) Dijkstra(best)
O(VE) O(E+V2)O(E+V2) O(E + VlogV)
表一：两种演算法解决 Single-Source Shortest Path 之时间复杂度

若再加上「以每个vertex为起点」的运算成本，更新成表二：

Bellman-Ford Dijkstra(worst) Dijkstra(best)
O(V2E)O(V2E) O(EV+V3)O(EV+V3) O(EV+V2logV)O(EV+V2logV)
表二：两种演算法解决 All-Pairs Shortest Path 之时间复杂度

还有一个条件：观察Adjacency Matrix发现，edge最多的情况，即为矩阵中除了对角线(diagonal)为0，其余皆有值的情况，因此edge数目E与vertex数目V应具有以下关系：E=O(V2)E=O(V2)
将此关系代入表二，形成表三：

Bellman-Ford Dijkstra(worst) Dijkstra(best)
O(V4)O(V4) O(V3+V3)O(V3+V3) O(V3+V2logV)O(V3+V2logV)
表三：两种演算法解决 All-Pairs Shortest Path 之时间复杂度

根据表三，成本最高的情况发生在Bellman-Ford Algorithm，需要 O(V4)O(V4) 的成本，而Dijkstra’s Algorithm虽然非常有效率，只需要 O(V3)O(V3)，但是不要忘记，唯有Graph中不存在具有negative weight的edge时，才可使用Dijkstra’s Algorithm，这将是一大限制。

而本篇文章将要介绍的Floyd-Warshall Algorithm，适用的情况只需要「Graph中不存在negative cycle」，即可在时间复杂度 O(V3)O(V3) 完成。

Floyd-Warshall 算法
若用一句含有逗点的话来描述Floyd-Warshall Algorithm的精髓，应该可以这么说：

每次多加入一个「中继点(intermediate vertex)」，考虑从vertex(X)走向vertex(Y)的最短路径，是否因为经过了该中继点vertex(Z)而降低成本，形成新的最短路径。
中继点就是「允许被路径经过」的vertex。
若原先的最短路径是 Path : X − Y，在引入中继点 vertex(Z)后，最短路径就有两种可能，Path : X − Y 或者 Path : X − Z− Y。


具体的过程可以看 All-Pairs Shortest Path：Floyd-Warshall Algorithm。非常详细，内容非常容易理解好。

关于程序
初始内容
看来程序，大概了解了具体的实现过程。先看一下程序中的重要循环部分：

for (int k = 0; k < num_vertex; k++) {
std::cout << "\nincluding vertex(" << k << "):\n";
for (int i = 0; i < num_vertex; i++) {
for (int j = 0; j < num_vertex; j++) {
if ((Distance[i][j] > Distance[i][k]+Distance[k][j])
&& (Distance[i][k] != MaxDistance)) {
Distance[i][j] = Distance[i][k]+Distance[k][j];
Predecessor[i][j] = Predecessor[k][j];
}
}
}
}
下面的图是初始化后的图，图中的矩阵记录了各个“相邻”结点的权重。例如：(A, B) = 2、(C, D) = 1。



分析
1，算法的核心思想是不断加入“中继点”。那是加入多少个，如何加入呢？

把所有的结点全部都加入
加入顺序无所谓
2，在每加入一个中继点后，都对矩阵中所有点，都做一次比较：

Distance[i][j] > Distance[i][k]+Distance[k][j]

其中 k 就是每个次加入的中继点。i, j 就是矩阵中每个点的坐标。对于一个中继点，要对每个点做一次比较，所以用一个双层嵌套循环(i, j) 来循环每个节点。因为每个中断点都要做一次，所以在双层嵌套循环(i, j) 外面再加一个循环(k)，变成三层循环，来计算所有的可能性。

3，矩阵中一些无穷大的点，在进行加入中继点的相关处理后，会变成有具体。那么是如何做的呢？
例如：加入结点 C 后，[B, A] 的位置的值，应该从“无穷大”变成“4”。过程如下：
前提：

假设结点加入的顺序是 A、B、C、D 的顺序
并且 A 加入完了，该加入B了
(1) 当 i = 1，j = 0 时，应该计算 [B, A]了。这时因为应该加入结点 B 了，所以 k = 1。则 Distance[i][j] > Distance[i][k]+Distance[k][j] 为：

Distance[1][0]（无穷大） > Distance[1][1]（0）+ Distance[1][0]（无穷大）

因为 Distance[1][0] = 无穷大，所以无法计算值，[B, A] 还是无穷大。

(2) 在 i = 1，j = 0 的条件下，把所有点都循环完后，该结点 C 变成中继点了，这时 k = 2。循环又到了 i = 1，j = 0 时，Distance[i][j] > Distance[i][k]+Distance[k][j] 为：

Distance[1][0]（无穷大） > Distance[1][2]（-2）+ Distance[2][0]（4）

这时候 Distance[1][2]（-2）+ Distance[2][0]（4）= 2，2 小于 无穷大，则把 2 设置到 [B, A] 上。

注意，有的结点无输出路径，则一直都是无穷大，例如：[D, A]、[D, B]、[D, C]。

所以，这个算法最后可以简单的说成：

把所有结点都当成中继点加入一次；每次加入中继点后，把所有的矩阵的中的点，都进行松弛一次。

第二十六章 最大流
在某个污水处理厂的某一道程序里，有一个「进水孔」，和一个「排水孔」，中间由许多「孔径不一」的水管连接起来，因为水管的「孔径大小」会影响到「每单位时间的流量」，因此要解决的问题，就是找到每单位时间可以排放「最大流量( flow )」的「排水方法」。


26.1 流网络
流网络有以下性质

流网络 G=(V, E) 是一个有向图，图中每一条边 (u, v) ∈ E 有一个非负的容量值 c(u, v) ≥ 0
如果边集合 E 包含一条边 (u, v)，则图中不存在反方向的边 (v, u)
如果边(u, v) ∉ E，则 c(u, v) = 0
图中不允许自循环
在流网络的所有结点中，有两个特殊结点：源结点 s 和 汇点 t。为方便起见，假定每个结点都在从源结点到汇点的某条路径上。也就是说对于每个结点 v ∈ V，都包含一条路径 s->v->t。因此，流网络是连通的。
除源结点外，每个结点都至少有一条进入的边，所以有 |E| ≥ |V| -1




如果解决反平行边问题
上面的性质中有“如果边集合 E 包含一条边 (u, v)，则图中不存在反方向的边 (v, u)”，这两个边称作“反平行”。如果存在这样的问题，如何解决呢？


具有多个源结点和多个汇点的网络



26.2 Ford-Fulkerson方法
为什么叫做“方法”而不是“算法”呢？因为它包含了几种运行时间各不同的具体实现，Ford-Fulkerson方法依赖于三种重要的思想，他们与许多流算法和问题有关，如残存网络、增广路径和切割。这些思想是最大流最小切割定理的精髓。Edmonds-Karp 是一个具体实现。

几个重要的概念
Residual Networks(残存网络)
Residual Networks的概念为，记录Graph上之edge还有多少「残存的容量」可以让flow流过。

以图三(a)为例，若在Path:S−A−C−D−T上的所有edge都有6单位的flow流过，那么这些edge(edge(S,A)、edge(A,C)、edge(C,D)、edge(D,T))的可用「残存capacity」，都应该要「减6」，例如，edge(S,A)只能「再容纳9−6=3单位」的flow，edge(C,D)只能「再容纳7−6=1单位」的flow。

这些「残存capacity」就称为residual capacity，以cf表示。
若edge(X,Y)上有flow流过，f(X,Y)，便将edge(X,Y)上的residual capacity定义为：

cf(X,Y)=c(X,Y)−f(X,Y)

c(X,Y)为原来水管孔径大小；
f(X,Y)表示目前水管已经有多少流量；
cf(X,Y)表示水管还能再容纳多少流量。


Residual Networks也是一个directed graph，其中：

vertex集合与原directed graph完全相同；
edge之capacity以residual capacity取代，见图三(a)右。
最关键的是，若「从vertex(A)指向vertex(C)」之edge(A,C)上，有6单位的flow流过，f(A,C)=6，那么在其Residual Networks上，会因应产生出一条「从vertex(C)指向vertex(A)」的edge(C,A)，并具有6单位的residual capacity，cf(C,A)=6。

因为Skew symmetry，f(C,A)=−f(A,C)；
再根据定义，cf(C,A)=c(C,A)−f(C,A)=c(C,A)+f(A,C)=0+6=6，
产生的“从 C 指向 A”的边其物理意义呢？可以用「如果想要重新配置水流方向」来理解。

举例来说，如果现在想经过Path:S−C−A−B−T流过2单位的flow，若观察最一开始「还没有flow经过」的directed graph(图二(a))，其实并不存在从vertex(C)指向vertex(A)的edge(C,A)，因此c(C,A)=0，但是因为在图三(a)已经有6单位的flow从vertex(A)流向vertex(C)，使得现在可以从edge(A,C)上把2单位的flow「收回」，转而分配到edge(A,B)上，而edge(A,C)上，就剩下4单位的flow，最后的结果如图三(b)左所示。
在新增一条「增加flow的Path」后，Residual Networks更新如图三(b)右。


也可以看 数据结构与算法分析 - 网络流入门（Network Flow） 中的向边说明，也很好地说明了残存网络里多加的这个边的意义。这个说明还与下面要讲的内容有，建议看看。

Augmenting Paths(增广路径)
在Residual Networks里，所有能够「从source走到termination」的路径，也就是所有能够「增加flow的path」，就称为Augmenting Paths。


若以图四(a)的Residual Networks为例，见图四(b)，Augmenting Paths有许多可能，例如：

Path : S−A−B−T，3单位的flow。
因为在路径上，所有edge中最小的capacity为c(A,B)=3，因此，flow可以容许从1单位到3单位。
Path : S−C−B−D−T，2单位的flow。
同理，因为在路径上，所有edge中最小的capacity为c(B,D)=c(D,T)=2，因此，flow可以容许1单位或2单位。
以及其他。

综合以上可以确定，以图四(c)为例：
若要看当前流入termination的「总流量」，要在图四(c)左，edge上标示「flow/capacity」的Graph上找。
如图四(c)，流入vertex(T)的总flow为8单位。
若要找「还能够增加多少流量」，也就是找Augmenting Paths，需要在Residual Networks上找，如图四(c)右。
若在Path:S−A−B−T、Path:S−A−C−D−T、Path:S−C−B−T流入「不超过该路径上最低residual capacity」之flow，都是图四(c)上的Augmenting Paths。


算法过程
Ford-Fulkerson Algorithm(若使用BFS搜寻路径，又称为Edmonds-Karp Algorithm的方法如下：

在Residual Networks上寻找Augmenting Paths。
若以BFS()寻找，便能确保每次找到的Augmenting Paths一定经过「最少的edge」。（这一步很重要，可以使用深度优先或广度优先，这里使用的是广度优先，下面会讲使用它的好处。）
找到Augmenting Paths上的「最小residual capacity」加入总flow。
再以「最小residual capacity」更新Residual Networks上的edge之residual capacity。(这个更新可能是增加也可能是减少)
重复上述步骤，直到再也没有Augmenting Paths为止。
便能找到Maximum Flow。



为什么使用广度优先算法查找增广路径

上面的说明如果看不太明白，也可以看一下 数据结构与算法分析 - 网络流入门（Network Flow） 这篇文章。

所以，如果使用“广度优先”算法，找一条从源结点到汇点的“最短路径”，就会找到 s->u->t 和 s->v->t 路径。但如果使用“深度优先”的话，就会像上面一样找到 s->u->v->t 和 s->v->u->t。

使用广度优先算法的 Ford-Fulkerson 方法称作“Edmonds-Karp算法”。

没有用上BFS，称为Ford-Fulkerson Algorithm，时间复杂度O(E|f|)。
其中，E为Graph上的edge数；
|f|为「最大流量」。
有用上BFS，称为Edmonds-Karp Algorithm，时间复杂度 O(VE2)O(VE2)。
26.3 最大二分匹配
一些组合问题可以很容易地表述为最大流问题。26.1 节的“多源结点多汇点”最大流问题就是一个例子。其它一些组合问题在表面上似乎与流网络没有多少关系，但实际上却能够归约到最大流问题。

参考学习：
算法9-6：最大流的应用

最大二分匹配问题
最大二分匹配问题特点如下：

对于一个二分图 G=(V, E)，结点集划分 L 和 R 两个集合，L ∪ R = V。
L 和 R 中的结点，只能和另一个集合里的结点连接，但 L 和 R 各自集合内的结点不相连。
如果 L 和 R 集合连接中有一条边，就是算是一个“匹配”。边都是单向的，都是从 L 向 R 或都是 从 R 向 L。
二分图中寻找最大匹配问题有着许多实际应用。例如，一个机器集合 L 要同时执行的任务集合 R 匹配。E 中有边(u, v) 就说明一台特定的机器 u ∈ L 能完成一菲特定的任务 v ∈ R。最大匹配能够让尽可能多的机器运行起来。


如何解决
对于一个二分图，令已有的边的容量（Capacity）为无穷大，增加一个源点s和一个汇点t，令s和t分别连接二部图中的一个分步，并设置其容量为1。这时得到流网络G’，计算得到的最大流就等于最大二分匹配。

注意：这里不像上面的“具有多个源结点和多个汇点的网络”问题。“具有多个源结点和多个汇点的网络”问题路径上的权重有大有小。这个问题是解决“是否能最大可能性地匹配上”的问题，所以所有的权重都是 1。所以和 s 与 t 连接的路径的权重都设置成 1 。


参考：图的匹配问题与最大流问题(五)——计算二分图的最大匹配

todo
如果边集合 E 包含一条边 (u, v)，则图中不存在反方向的边 (v, u)，但是在例子中有呀。

24.1

做完了，就是求从一个点到图中任意一个点的权重最少的路径（带负值）的

todo：

为什么没有边 (x,t)
为什么执行 |V|-1 次
为什么广度优先些算法 和 深度优先算法 和这下面的图算法有关？看一下细节

常用符号：∈ ∉ ⊂ ⊄ ⊆ ⊃ ⊇ ∪ ∩

¡™£¢∞§¶•ªº–≠œ∑®†¥øπ“‘‘‘«åß∂ƒ©©˙˙∆˚˚¬¬…ææ

Ω≈ç√∫∫µµµ≤≤≥≥÷÷

⁄€‹›fifl‡°·‚—±Œ„´‰Á¨ˆØ∏”’”’»ÅÍÎÏ˝ÓÔÒÚÆÆÆÆÆÆƸ˛Ç◊ı˜Â¯˘˘˘˘¿

广度和深度的区别
广度用循环即可，深度需要用递归