Sol'n in directed weighted cyclic graph to terminating vertex: such that all vertices along path have same independently given solution?

Question

We’re trying to work out if, using a directed weighted cyclic graph, with one (in this example) ‘terminating’ vertex ‘Z’ (but potentially other terminating vertices are available):

Is it possible to find a path:

1. from any other vertex
2. to the terminating vertex (if such a path exists)
3. such that any visited vertex along that path
4. also guarantees the same (sub) solution
5. to the terminating vertex
6. as if it had independently been asked to solve its own path

Loops are avoided by abandoning and backtracking if a vertex that has already been visited is encountered again.

For the purposes of the example below, the weights are ‘orders’ so that 1 is preferential to 2.

The example shows a solution to 1,2 (from the constraints above) starting from two different vertices - A and C, C gives a preferential solution to its sub-path from A going to F and then Z, whereas starting at A gives a long-winded solution because of the priority from A-B. In this case we would prefer the solution from A to F to Z if the starting vertex was A, as well. This does not satisfy the constraints given in 3,4,5 or 6 above since A is in the sub-path of C-D-A-F-Z and the independent solution from A is A-B-C-D-E-F-Z.

So - the path from A to Z via F (marked with ===) should always be used, but it is possible to find a route A-B-C-D-E-F-Z from A if the priority weight (1) is tried first, which of course it will be.

Note that we assume this is a "best" solution (even though it does not take the priority route from A to Z) because it is the shortest route - this is a point that we are not totally sure is and for the purposes of this question assume the "best" path is one that satisfies all the constraints above.

    *C ------2---→ D ------2-----→ E
    | ↑            |               |
    1 1            1               1
    ↓ |            ↓               ↓
     B ←-----1----*A ======2=====→ F ====1====→ Z

Erroneous solution from *A:

     C ------2---→ D ------2-----→ E
     ↑                             |
     |                             1
     |                             ↓
     B ←-----1----*A               F ---------→ Z

Natural solution from *C:

    *C ------2---→ D                E
                   |
                   |
                   ↓
     B             A -------------- F --------→ Z

Desired solution from *A:

     C             D                E



     B            *A -------------- F --------→ Z

We propose that having found a solution from e.g. A to Z, in order to satisfy constraints 3,4,5 and particularly 6, then one could backtrack along each vertex in the solution and resolve from there, and check if the resulting solution from that vertex (which may be different because the ‘which vertices are visited’ list will now be empty) is a sub-path of the original solution. If any sub-path does not match then we would backtrack to a vertex before the one last tried and resolve the original path from there.

The concern with this algorithm is that we may completely eliminate certain solutions to the path finding from any vertex to the terminator even when one exists, because of this check of the sub-paths from each traversed vertex having to match a ‘super’ path if they were asked to solve themselves independently. I.e. that there would be no super path that for each vertex within would have the same first-given independent solution from those inner vertices as part of it. We have no proof that this is not going to happen but it seems to be the type of problem a graph expert will know so we humbly pose it to the community…

So the question is: Is it possible to find a solution from any vertex in a directed weighted cyclic graph to a terminating vertex (should any path to a subset of terminating vertices exist) such that all vertices along that path have the same independently given (sub) solution to that same terminating vertex. If so, are there known/named algorithms to achieve this solution?

Answer 1

Fix an arbitrarily chosen numbering of the edges. At each vertex, Find all minimal paths to $Z$ and collect the first edges from them. From this collection, choose the lowest numbered edge as the next edge you will take. Repeat until you reach $Z$.

I.e., you just find minimal paths, and use the numbering to break any ties.