[关闭]
@zqbinggong 2018-03-24T05:14:55.000000Z 字数 3228 阅读 550

chap25 所有结点对的最短路径问题

矩阵乘法 Floyd-Warshall算法 Johnson算法 算法导论

内容


概览

  1. 前驱结点矩阵,,其中给出从结点i到结点j的耨条最短路径上的结点j的前驱结点
  2. 前驱子图,其中,即i和i能够到达的结点集,即点集中该点和他的前驱组成的边集
  3. print-path(Pi,i,j)

.

if i == j
    print i
else if pi[ij] = nil
    print no path
else
    print-path(Pi,i,pi[ij])
    print j

最短路径和矩阵乘法

  1. 最短路径的结构,基于引理24.1,最短路径的子路径也是最短路径
  2. 迭代关系:
  3. 其中表示从结点i到结点j的至多包含m多条的任意路径中的最小权重,因而当m=n-1时,就是原问题的解
  4. 根据迭代关系的形式,基于动态规划的思想,并使用重复平方技术来计算

extended-shortest-paths(L,W)

n = L.rows
let L' to be a new n by n matrix
for i = 1 to n
    for j = 1 to n
        l'[ij] = 00
        for k = 1 to n
            l'[ij] = min(l'[ij], l[ik]+w[kj])
return L'

使用重复平方技术——
faster-all-pathsirs-shortest-paths(W)

n = W.rows
L_1 = W
m = 1
while m < n-1
    let L_2m = extended-shortest-paths(L_m,L_m)
    m = 2m
return L_m

Floyd-Warshall算法

  1. 条件:不存在权重为负值的环路
  2. 仍然是动态规划的思想,但是用另一种动态规划公式来求解,或者说对子问题的空间划分不同。上面的算法,它是以最短路径包含的边数的最大值作为问题空间的规模;而这里,将最短路径包含的中间节点所属的集合的作为子问题的问题空间,集合的大小便是问题空间的规模
  3. 这里的集合是有限制的,即大集合包含小集合。具体做法就是对所有结点编个号,然后大规模的集合ei比是小规模的集合并上那些大编号的结点
  4. 思考下,为什么两种动态规划的时间相差一个量级(不考虑重复平方技术)呢?

    • 个人认为,原因还是在于动态规划降低复杂度的本质在于减少重复运算。因而后者定是对于重复计算的利用率高,直观上来看,后者的做法与chap15中LCS的操作流程基本一致
    • 前者对于边的条数的考虑,并没有使得小规模的问题的结果得到利用,因为原问题的解和边的条数并不是直接相关的,当然得到小问题的边数和得到小问题的中间结点个数是等价的,二者都很难直接利用,但是后者在得到中间结点个数的同时,还因为子问题空间即中间结点集的包含关系,使得后者在获得中间结点个数的同时还得到了更多的信息,而这种信息,使得子问题的解得到更加充分的利用
    • 简单说就是,前者所分成的子问题的解和原问题的求解方向相关性较差,而后者相关性高(这里求解方向意思是:大问题求解5的阶乘,小问题相关就是在求3的阶乘,不相关就是求3的平方,相关性差就是求
    • 补充:概括说就是,前者的子问题空间并没有相关性,边数不同的边集是不确定的,只知道这个集合里有几条边,但是包含哪些边并不清楚;而后者子问题集之间有依赖关系,根据这种关系,问题空间被不断细化,这与chap15中典型动态规划的算法的做法是一致的
    • 因而结论就是在利用动态规划思想时,要尽量以和原问题的解相关的量构建关系式,如这里的中间结点集合,;在划分子问题时,应该尽量让子问题空间之间具有明显的依赖关系,这样在问题回溯时能方便地得到大问题的解
  5. 关系式:

  6. 一些细节,注意k的上限是n,不是n-1,如果是n-1的话,那么将因无法考虑包含中间结点n的情况而可能出错

自底向上
floyd-warshall(W)

n = W.rows
D_0 = W
for k = 1 to n
    let D_k be a new matrix
    for i = 1 to n
        for j = 1 to n
            5中关系式
return D_n

有向图的传递闭包

  1. 有向图的传递闭包为,其中
  2. 方法1,使用Floyd-Warshall算法,将边的权重赋为1,去寻找那些d为有限值的(i,j)
  3. 方法2: 在实际场景中能够比1节省时间和空间,使用逻辑或操作和逻辑与操作来代替FW算法中min和+
  4. 关系式:

    对于

transitive-closure(G)

n = |G.V|
let T_0 be a new matrix and initialize it obey formula dexcribed as 4
for k = 1 to n 
    let T_k be a new matrix
    for i = 1 to n
        for j = 1 to n
            关系式4
return T_n

稀疏图——Johnson算法

  1. 条件:不存在权重为负值的环路
  2. 基于Dijksrtra算法,使用菲波那切最小有限队列则复杂度为,使用二叉最小堆的复杂度为
  3. 为了满足Dijkstra算法对于边权重为非负数的要求,当存在负权重时,需要重新赋予权重以满足要求
  4. 基于引理25.1,做法是在原图上加上一个结点s,并加上s和所有原图中结点相连的权重为0的有向边。算法第一步及时使用Bellman-Ford算法以s为源结点求出所有的,h即为引理中的“任意函数”
  5. 伪代码:

Johnson(G,w)

compute G'
if bellman-ford(G',s) == false
    print "the input graph contains a negative-weight cycle"
else
    for each vertex v in G.E
        set h(v) to the value computed by the bellman-ford algorithm
    for each edge(u,v) in G'.E
        w'(u,v) = w(u,v) + h(u) - h(v)
    let D be a new n by n matrix
    for each vertex v in G.E
        run dijkstra(G,w',u) to compute delta(u,v) for all v in G.V
        for each vertex in G.V
            d[uv] = delta(u,v) + h(v) - h(u)
return D

习题

to be continued


代码实现

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注