Shortest path that traverses a list of required edges

Question

I have a directed graph, that looks like this:

I want to find the cheapest path from Start to End where the orange dotted lines are all required for the path to be valid.

The natural shortest path would be: Start -> A -> B -> End with the resultant cost = 5, but we have not met all required edge visits.

The path I want to find (via a general solution) is Start -> A -> B -> C -> D -> B -> End where the cost = 7 and we have met all required edge visits.

Does anyone have any thoughts on how to require such edge traversals?

Answer 1

Let R be the set of required edges and F = |R|. Let G be the input graph, t (resp. s) the starting (resp. ending) point of the requested path.

---

Preprocessing: A bunch of Dijkstra's algorithm runs...

The first step is to create another graph. This graph will have exactly F+2 vertices:

• One for each edge in R
• One for the starting point t of the path you want to compute
• One for the ending point s of the path you want to compute

To create this graph, you will have to do the following:

1. Remove every edge in R from G.
2. For each edge E = (b,e) in R:
   1. Compute the shortest path from t to b and the shortest path from e to s. If they exist, add an edge linking s to E in the "new graph", weighing the length of the related shortest path.
   2. For each edge E' = (b', e') in R \ {E}:
      1. Compute the shortest path from e to b'. If it exists, add an edge from E to E' in the new graph, weighing the length of that shortest path. Attach the computed paths as payload to the relevent edges.
      2. Attach the computed path as a payload to that edge

The complexity to build this graph is O((F+2)².(E+V).log(V)) where E (resp. V) is the number of edges (resp. vertices) in the original graph.

---

Exhaustive search for the best possible path

From this point, we have to find the shortest Hamiltonian Path in the newly created graph. Unfortunately, this task is a hard problem. We have no better way than exploring every possible path. But that doesn't mean we can't do it cleverly.

We will perform the search using backtracking. We can achieve this by maintaining two sets:

• The list of currently explored vertices: K (K for Known)
• The list of currently unknown vertices: U (U for Uknown)

Before digging in the algorithm definition, here are the main ideas. We cannot do anything else than exploring the whole space of possible paths in the new graph. At each step, we have to make a decision: which edge do we take next? This leads to a sequence of decisions until we cannot move anymore or we reached s. But now we need to go back and cancel decisions to see if we can do better by changing a direction. To cancel decisions we proceed like this:

• Every time we are stuck (or found a path), we cancel the last decision we made
• Each time we take a decision at some point, we keep track of which decision, so when we get back to this point, we know not to take that very same decision and explore the others that are available.
• We can be stuck because:
  • We found a path.
  • We cannot move further (there is no edge we can explore or the only one we could take increases the current partial path too much -- its length becomes higher than the length of the current best path found).

The final algorithm can be summed up in this fashion: (I give an iterative implementation, one can find a recursive implementation a tad easier and clearer)

Let K ← [], L[0..R+1] ← [] and U ← V (where V is the set of every vertex in the working graph minus the starting and ending vertices t and s). Finally let l ← i ← 0 and best_path_length ← ∞ and best_path ← []

While (i ≥ 0):

1. While U ≠ []
   1. c ← U.popFront() (we take the head of U)
   2. L[i].pushBack(c)
   3. If i == R+1 AND (l == weight(cur_path.back(), s) + l) < best_path_length:
      1. best_path_length ← l
      2. best_path ← cur_path
   4. If there is an edge e between K.tail() and c, and weight(e) + l < best_path_length: (if K is empty, then replace K.tail() with t in the previous statement)
      1. K.pushBack(c)
      2. i ← i+1
      3. l ← weight(e) + l
      4. cur_path.pushBack(c)
2. Concatenate L[i] at the end of U
3. L[i] ← []
4. i ← i-1
5. cur_path.popBack()

At the end of the while loop (while (i ≥ 0)), best_path will hold the best path (in the new graph). From there you just have to get the edges' payload to rebuild the path in the original graph.