1. 加权有向图
1.1. 最短路径问题
加权有向图的边有了方向性,我们在这个模型下通常比较关注从一个结点到另一个结点的最短路径这一类问题,将它称为最短路径问题。
关于最短路径和加权有向图,我们有几个性质需要说明。
1.并非所有顶点都可达。
2.负权重会使得问题更加复杂。
3.最短路径通常是简单的,我们的算法会忽略构成环的零权重边。
4.最短路径不一定唯一。
5.可能存在自环和平行边。
6.我们的算法最终计算结果会得到一个最短路径树SPT,包含从s出发所有可达的顶点。
1.2. 实现加权有向图
1.2.1. 实现加权有向边
要实现加权有向图,其实和之前的加权无向图相差不大,甚至更加简单。我们首先实现加权有向边。我们给它准备的接口如下,与无向的相差不大。
1 | class DirectedEdge |
接口实现为:
1 | DirectedEdge::DirectedEdge(int v = 0, int w = 0, double weight = 0.0) |
1.2.2. 实现加权有向图
大体上与加权无环图相同。接口和实现如下。
1 | class EdgeWeightedDigraph |
实现:
1 | EdgeWeightedDigraph::EdgeWeightedDigraph(int V) |
2. 最短路径算法
2.1. 理论准备
2.1.1. 松弛
对于最短路径的数据结构,我们依然沿用之前的edgeTo,distTo的模式。我们把主要关注点放在一种新的基本操作即松弛上,它是我们后面算法的操作的基本单元之一。
松弛操作的具体内容是对一条边v→w,如果当前存放的起点到v的距离(distTo[v])加上v→w的权值小于起点到w的距离(distTo[w]),则替换之(distTo[w] = distTo[v] + e.Getweight())。核心代码如下。
1 | void relax(EdgeWeightedDigraph G, int v) |
2.1.2. 最短路径的充要条件
在松弛操作的基础上,我们的算法理论基础是如下命题:对于一幅加权有向图,数据结构如上文所示。对于所有从起点s可达的点v,distTo[v]是从s到v的某条路径长度,不可达时值为无穷大。那么对于从v到w的任意一边e,distTo[w] <= distTo[v] + e.Getweight()是这些边是最短路径的充要条件。
证明如下:
必要性:
如果全是最短路径,对于从v到w如果存在一边e,distTo[w] > distTo[v] + e.Getweight(),那么显然与假设矛盾。
充分性:
假设有最短路径s→a→…→b→w。e1, e2, …,ek是对应两结点的某个边。现在有如下性质:
distTo[w] <= distTo[b] + ek
…….
distTo[a] <= distTo[s] + e1
其中distTo[s] = 0.0,所以求和后得到distTo[w] <= 最短路径长度。而显然其又>=最短路径长度,所以distTo[w]为最短路径长度。证毕。
2.1.3 通用算法
在以上充要条件的基础上,我们可以推导出一个通用的求最短路径的算法:将distTo[s] = 0.0,将其他的distTo[]初始化为无穷大。然后不断放松所有不满足充要条件的边,直到没有这样的边存在。其证明略。
2.2. Dijkstra算法
这个算法与我们上一节的Prim算法又很多相似之处,它也会构造一棵树,是最短路径树。算法的原理是把起点加入树中,然后不断地把非树顶点中distTo[]最小的进行放松然后加入树中,直到所有顶点都在树中或者所有非树顶点的distTo[]都是无穷大。
证明:
对每个可达顶点v使用松弛时,都会使得它满足充要条件的局部distTo[w] <= distTo[v] + e.Getweight(),这个松弛过程不会产生比distTo[v]更小的distTo[w],而由于按照最小顺序,所以后续松弛不可能再次改变distTo[v]。那么算法结束后,充要条件成立。
代码如下:
1 | class Dijkstra |
其算法,空间消耗与V成正比,时间消耗与ElogV成正比。
2.3. 无环加权有向图的最短路径
同样是放松边如果我们按照拓扑排序来放松顶点,同样也能达到效果。而且消耗时间与E+V成正比。证明同上,原理相同。代码绝大部分也与之相同,不同的部分只是把邮箱队列替换成了拓扑排序序列。
1 | class AcycliSP |
2.4. 并行任务调度问问题
并行任务调度问题,指一组任务被制定了优先级顺序和任务完成所需时间,需要求得最短的时间消耗的任务安排,处理器有多个。其解决方法为:将任务关系构造为一幅加权无环有向图(起点终点单独构造,每个任务开始和结束分别为一个顶点,二者间的边的权重为任务消耗时间,优先级限制变为一个0权重的边)。然后找到它的从起点到终点的最长路径,就是最佳安排,消耗的时间也是最短时间。
证明:
对于这情景,画好图的模型后,可以看出来图的走向,根据优先级关系限制画出来的图,每一个顶点的可达路径对应的累积权值实际上已经是这个顶点的任务开始时间的下限,在这个情况下,到达终点所用的最长时间(要满足所有任务都能被完成),就是最短耗时。而最长路径的算法在上面的基础上将数值曲取相反数relax方里面改比较符号就可以实现了。此处代码略。
2.5. 一般方法
最短路径问题的一般解决办法是Bellman-Ford算法,在任意含有v个顶点的加权有向图中给定起点s,从s无法到达任何负权重环,那么,将distTo[s]初始化为0,其他为无穷大就可以任意顺序发送图的所有便边,重复v轮。代码十分的简洁。 其中由于每一次放松都会有很多点放松失效,只有上一个顶点被放松时改变了distTo[]值的,才会对其进行放松。我们用一个队列来装入改变了distTo的顶点。检测负权重环的原理与之前的相同,只要检测到放松v轮后还有点在队列中,则必定有换环。
1 | class BellmanFord |