shortest tree path vertex

Question

We have a directed graph G(V, E) with positive weights on the edges, as source vertex s and a destination t. Also, the shortest s − t path includes every other vertex in the graph. I need to compute alternate shortest path distances between s and t in case some edge e ∈ E is removed. I want to design an O(E^2 log V) algorithm that computes, for all e ∈ E, the shortest s − t path distance in the graph G \ e. The final output should be an array of size E where the entry for edge e should contain the shortest s − t path distance in G \ e.

Answer 1

Consider the S-T path ("backbone" in the following) and number the K vertices in path order, with S as vertex 1.

• S₁ -> V₂ -> ... -> V_K-1 -> T_K

Define BB_i-j as the subpath with adjacent vertices from i to j of the original path, including edges in between.

Since all vertices in G belongs to the path, then all edges in G are between two different vertices in the path, name e_i->j the directed edge from i to j.

Removing an edge from the graph, the only relevant case is when the edge is part of the backbone, in all other case the path does not change.

Removing an edge e_i->j from the backbone will break it, so only in this case we need to find a replacement, we can demonstrate that the new minimum shortest path has the form

• BB_1-i' -> e_i'->j' -> BB_j'-K with i'<=i and j'>=j

demonstration left as exercise ;-)

After the replacement the path length is increased by the additional length

• AL(e_i->j) = weight of e_i->j - weight of subpath B_i-j

Our goal is to find a valid replacement edge with the minimum additional cost, here the pseudocode:

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

Complexity:

• first two loops iterate over all edges, that is O(|E|)
• calculation of al is O(1)
• search in BT, since |BT| <= |V| is O(log |V|) for every iteration
• removing edges from BT, each edge can be inserted and removed only once from the tree so, in total for all iterations, O(|E| log |V|)

In total we have O(|E| log |V|)

Note that the problem does not require to generate the path, but just to calculate the distance, if the path must be generated then the complexity increases, since we can have at most |E| paths of length |V|, then O(|E| |V|)