The shortest path that crosses the list of required edges

I have a directed graph that looks like this:

Graph

I want to find the cheapest way from Start to finish , where all the orange dashed lines are needed for the right path.

The natural shortest path would be: Start → A → B → End with a total cost = 5, but we did not complete all the necessary extreme visits.

The path I want to find (through the general solution) is Start → A → B → C → D → B → End , where the cost = 7, and we have completed all the necessary extreme visits.

Does anyone have any thoughts on how to demand such bypasses of the region?

+6
source share
1 answer

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


Pre-processing: Dijkstra's algorithm chain is running ...

The first step is to create another schedule. 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 calculate
  • One for the endpoint s of the path you want to compute

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

  • Remove all edges from R from G.
  • For each edge E = (b, e) in R:
    • Calculate the shortest path from t to b and the shortest path from e to s. If they exist, add the edge connecting s to E in the "new graph", weighing the length of the corresponding shortest path.
    • For each edge E '= (b', e ') in R \ {E}:
      • Calculate 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 this shortest path. Attach the calculated paths as the payload to the corresponding edges.
      • Attach the calculated path as a payload to this edge

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


An exhaustive search for the best way

From this point we must find the shortest Hamiltonian path in the newly created graph. Unfortunately, this task is a complex problem. We have no better way than to explore all possible paths. But this does not mean that we cannot do it smartly.

We will perform a search using reverse tracking. We can achieve this by supporting two sets:

  • List of currently reviewed peaks: K (K for known)
  • List of currently unknown peaks: U (U for Uknown)

Before digging into the definition of an algorithm, here are the main ideas. We can do nothing but study the entire space of possible paths in a new graph. At each step, we must make a decision: what edge will we do next? This leads to a sequence of decisions until we can no longer move, or we reach s. But now we need to go back and reverse decisions to see if we can do better by changing direction. To reverse decisions, we do the following:

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

The final algorithm can be summarized as follows: (I give an iterative implementation, you can find a recursive implementation a little simpler and more understandable)

Let K[] , L[0..R+1][] and U ← V (where V is the set of each vertex of the working graph minus the initial and final vertices t and s). Finally, let li ← 0 and best_path_length ← ∞ and best_path[]

So far ( i ≥ 0):

  • Bye U[]
    • cU.popFront() (let's take the head of U)
    • L[i].pushBack(c)
    • If i == R+1 AND ( l == weight ( cur_path.back() , s) + l ) < best_path_length :
      • best_path_lengthl
      • best_path ← cur_path
    • If there is an edge e between K.tail() and c , and weight(e) + l < best_path_length : (if K empty, then replace K.tail() with t in the previous statement)
      • K.pushBack(c)
      • ii +1
      • lweight(e) + l
      • cur_path.pushBack(c)
  • Concatenation L[i] at the end of U
  • L[i][]
  • ii -1
  • cur_path.popBack()

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

+2
source

Source: https://habr.com/ru/post/981494/


All Articles