chap24 单源最短路径

松弛操作 Bellman-Ford算法 Dijkstra算法 差分路径 算法导论

内容

最短路径

1. 最优子结构（引理24.1）：两个结点之间的一条最短路径包含着其他的最短路径
2. 最短路径的表示：通过前驱子图，本章的算法在终止时，所生成的$G_{\pi }$是一棵“最短路径树”。注意最短路径不是唯一的，因而最短路径树也不一定是唯一的
3. 松弛技术，基于引理24.1的思想。
4. 最短路径和松弛操作的性质
   
   • 24.10 三角不等式：
   • 24.11 上界性质：v.d只能大于或者等于s到v的最短距离
   • 24.12 非路径性子： s不能到达的点的d为00
   • 24.14 收敛性质：
   • 24.15 路径松弛技术
5. 松弛技术的伪代码：

relax(u,v,w)——对边(u,v)进行松弛操作

if v.d > u.d + w(u,v)
    v.d = u.d + w(u,v)
    v.p = u

initialize-single-source(G,s)——选定源结点，进行属性d的初始化

for each vertex in G.V
    v.d = 00
    v.p = nil
s.d = 0

Bellman-Ford算法

1. 注意，与Dijkstra相比，该算法有点像深度优先搜索和广度优先搜索的区别，前者像是往外扩散的，后者像是一条路走到底。
2. 适用条件：一般情况下的单源最短路径问题，即边权重可以为负值，但不能有负值环路。当条件不满足时，算法返回false，否则返回最短路径和他们的权重
3. 该算法会对图的每条边进行V-1次处理，然后再对每条边进行检查，看是否存在负值环路。
4. 该算法能得到最短的路径的关键在于，松弛操作的if条件，它使得一条路径（u，v）能进行松弛的前提是u.d已经被更新，不再是00.在这个前提下，由于任何一条最短路径$p=<v_{0},v_{1}...v_{k},,>$最多包含V-1个结点，并且在第$i$次循环中，松弛的是边$(v_{i-1},v_{i})$
5. 伪代码：

Bellman-Ford(G,w,s)

initialize-single-source(G,s)
for i = 1 to V-1
    for each edge(u,v) in G.E
        relax(u,v,w)
for each edge(u,v) in G.E
    if v.d > u.d + w(u,v)
        return false
return true

有向无环图中的单源最短路径

1. 根据结点的拓扑次序来对带权重的有向无环图进行边的松弛操作，可以在$\Theta(V+E)$时间内计算出从单个源结点到所有结点之间的最短路径
2. 注意到，其实关键还是与Bellman-Ford算法相同，即利用路径松弛性质。与Bellman-Ford做法不同，这里因为拓扑次序本身就保证了松弛操作的顺序是满足路径松弛性质中的松弛顺序的，因而无需进行更多的循环来确保路径松弛松弛性质中的要求得到满足
3. 由于拓扑次序的存在，减少了运算量
4. 伪代码：

dag-shortest-paths(G,w,a)

topologically sort the vertices of G
initialize-single-source(G,s)
for each vertex u, taken in topologically sorted order
    for each vertex v in G.adj[u]\
        relax(u,v,w)

Dijkstra算法

1. 适用条件：边权重为非负值的有向图
2. 该算法在运行过程中保持S中的结点都是已经找到最短路径的点，然后从剩下的结点中找到d值最小的结点加入S
3. 该算法基于收敛性质（$s\sim u \rightarrow v$），因而能得到最短路径的关键在于新加入的结点v的前驱必须在S中。再看算法寻找v的方式是寻找d值最小的结点，因而要求权重非负，否则d值最小的点的前驱不一定在S中即出现$s\sim u \rightarrow x\rightarrow v$且x不在S中的情况（$w(x,v)<0$）
4. 3中$s\sim u \rightarrow x\rightarrow v$情况的出现表示，存在边(z,v)且z在S中，否则v.d是00，其次当$v.d < x.d$时，若x仍然是最短路径上v的前驱，则必然是因为$w(x,v) < 0$,否则无需relax(x,v)
5. 伪代码：

Dijkstra(G,w,s)

initialize-single-source(G,s)
S = empty set
Q = G.V
while Q is not empty
    u = extract-min(Q)
    S = S U {u}
    for each vertex v in G.adj[u]   #这步操作导致了权重必须非负
        relax(u,v,w)

差分约束和最短路径

1. 线性规划：给定$m\times n$的矩阵A，m维向量b和n维向量c，使得在$Ax\leqslant b$的约束条件下优化目标函数$cx$
2. 我们的目标暂时停留在求解上，即寻找一个约束条件的可行解，而不是目标函数的解
3. 差分约束：矩阵的每一行只包含一个1和-1，其余为0，即约束条件转化成$x_{j} - x{_i} \leqslant b_{k}$
4. 将矩阵A看成是n个结点和m条边构成的图的邻接矩阵的装置，之所以装置就是为了将小于等于转化成大于等于，这样就变成了求解最短路径的等价问题。
5. 约束图$G = (V,E)$,除了3中对应的结点和边外，加上一个源结点s和s到n个结点的边（权重为零，其他边的权重为对应的b的值）
6. 定理25.9 以s为源结点的最短路径树中各个结点的属性d的值就是问题的一个可行解

习题

to be continued

代码实现