最短树路径顶点

Question

我们有一个边带正权的有向图G(V，E)，作为源顶点s，目标点T。此外，最短的s-t路径包括图中的每一个其他顶点。我需要计算s和t之间的交替最短路径距离，以防某些边e∈e被删除。我想设计一个O(e^2logV)算法，它计算图G\e中所有e∈e的最短S-T路径距离。最后的输出应该是一个大小为E的数组，其中edge E的条目应该包含G\E中最短的S-T路径距离。

Answer 1

考虑S-T路径（以下为“主干”），并按路径顺序对K个顶点进行编号，S为顶点1。

• s₁->v₂->...->v_k-1->t_k

定义BB_i-j为具有从原始路径的i到j的相邻顶点的子路径，包括中间的边。

由于G中的所有顶点都属于路径，所以G中的所有边都位于路径中两个不同的顶点之间，将E_I->J命名为i到J的有向边。

从图中删除边，唯一相关的情况是当边是主干的一部分时，在所有其他情况下路径都不改变。

从主干网中删除边E_I->J会破坏它，所以只有在这种情况下我们才需要找到替换，我们可以证明新的最小最短路径具有如下形式

null

作为练习的示范；-）

在替换之后，路径长度增加附加长度

• al(E_I->J)=E_I->J-子路径B_I-J
的权重

Glossary:
- v(i) is the i-th vertex in the backbone
- e(i->j) is the edge going out from v(i) to v(j), in the following we only
  consider edges e(i->j) with j>i, i.e. forward edges, singe backward
  edges can never be part of the solution
- e(*->k), k>j is any edge in the BT terminating in v(k) where k is greater
  than j, the first index is unspecified since edges in BT are only sorted
  by destination vertex
- e(*->q), q<j is any edge in the BT terminating in v(q) where q is lower
  than j, the first index is unspecified since edges in BT are only sorted
  by destination vertex
- BT a binary search tree where we store "best" edges found during the
  iteration, the unique key in BT is the destination vertex's index, so
  we can store here at most one incoming edge per vertex, BT is initially
  empty, during the iteration we buld it so that it has the additional
  property that given two edges e(*->a) e(*->b) in BT, if a<b then also
  AL(e(*->a)) < AL(e(*->b)); in fact BT is ordered at same time both
  by destination index and additional length of the edge
  BT invariants (thanks j_random_hacker): at all times, BT contains only edges that
  1. could be used to form a new path if e(i->i+1) is deleted (because they 
     begin at i or before, and end at i+1 or after)
  2. are not dominated by any other such edge. An edge e(i->j) dominates 
     another edge e(i'->j') if both j >= j' and AL(i->j) < AL(i'->j').
     If edge x dominates edge y, it means that, for each edge-deletion yet
     to be considered (e(i->i+1), e(i+1->i+2), etc.), any replacement path 
     that uses y can always be changed to a shorter path using x, so we don't
     need to care about y

//On each iteration we'll search the solution for removal of edge e(i->i+1)
for each vertex v(i) in S-T in path order, excluding T
  //Discard backward edges, since they can only increase the path length
  for each edge e(i->j) going out from v(i) directed to a vertex v(j) with j>i excluding the backbone edge
    calculate additional length AL(e(i->j))
    search BT using j as key, looking for an egde e(*->k) with k >= j
    if such an edge exists and AL(e(*->k)) <= AL(e(i->j))
      discard the current edge (BT's second property requires that)
    else
      //The current edge is the best choice to reach v(j)
      insert edge in BT (if k==j) discard e(*->k)
      //Now me must check if the new edge can also replace previous
      //ones in the BT to keep the second property valiud, for this we have 
      //to scan the BT in descending order and discard edges with AL >= than
      //the current one
      loop over edges e(*->q) in BT with q<j in descending order
        if AL(e(*->q))>=AL(e(i->j))
          discard e(*->q)
        else
          stop loop
      endloop
    end if
  end for each edge
  //Prune tree from useless edges
  remove from BT all edges with j < i+1
  if BT is empty
    no solution
  else
    select the first edge(i'->j') in BT ==> this is the replacement edge with minimum additional cost, so distance is dist(S-T) + AL(e(i'->j'))
end for each vertex

null

注意，这个问题并不需要生成路径，而只需要计算距离，如果必须生成路径，那么复杂度就会增加，因为我们最多可以有E条长度为V的路径，那么O（E V）