Modified Shortest path algorithm, forbidden paths

Question

We are provided with a graph G = (V, E), where each edge is associated with some positive weight (W[i] > 0). We are asked to find the shortest path from A to B provided we follow the following conditions :

We are also given some forbidden paths, say x. The goal is the shortest path should not contain any forbidden path as its sub-path.

For example: Consider a graph G with 4 vertices and 5 edges (1, 2, 1), (2, 1, 1), (1, 4, 5), (1, 3, 1.5), (3, 4, 1). Here, the 3rd entity in the bracket denotes the weight of edge between 'u' and 'v'. We are required to find the shortest path between 1 and 4, and the list of forbidden paths contains only the path 1->3->4.

The paths from 1 to 4 are 1 -> 4, 1 -> 2 -> 3 -> 4, 1 -> 3 -> 4.

Out of these, only 1st 2 are valid paths, and among them the shortest path is 1 -> 2 -> 3 -> 4 of total weight as 3.0.

Is there an efficient algorithm for the above task? Please describe the algorithm with the complexity analysis. I would be highly thankful if you could provide a code as well.

Alexey Guseynov · Accepted Answer · 2016-09-22 10:59:20Z

1

You can preprocess the graph in such a way to embed forbidden paths in-to it. For every forbidden path you duplicate vertices which belong to it and then drop some of the edges. That duplicates would have special meaning: walking along duplicated edge would mean that you have come to a vertex along the forbidden path and you can't walk along the last edge of it. If you are walking along original edges, then you have come somewhere to the middle of forbidden path so it does not affect you. To achieve that you drop all incoming edges to a duplicate path excepting edge to it's second vertex from it's first vertex. But you drop that edge from original path.

a forYou split vertices which are part of forbidden paths in-to several virtual vertices and drop some of the edges. Let's suppose that in following graph path ABC is forbidden:

A-->B-->C
D->/

Then you split B to BA and BD (depending from which vertex you have come to B) and drop BA->C edge.

A->BA  /->C
D->BD-/

Now you can use classic dijkstra on that preprocessed graph.

More complex example, let's suppose that ABCF is forbidden:

    G->\
A-->B-->C-->F
D->/ \->E

So we duplicate B and C as internal vertices of the forbidden route, we drop A->B edge and leave only A->B'. We also drop all other incoming edges to B' and C' but we leave B'->E edge because it drives away from forbidden route. We also drop C'->F edge.

 /->B'-->C'
|    \------->\
|              \
|   G->\        \
A   B-->C---->F  \
D->/ \----------->E

edited Sep 22, 2016 at 10:59

answered Sep 22, 2016 at 9:58

Alexey Guseynov

5,3441 gold badge24 silver badges30 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

caretaker Over a year ago

The graph is not visible.

caretaker Over a year ago

Could you please take a larger graph and explain how to modify the graph

Alexey Guseynov Over a year ago

I've expanded the answer.

eternal_learner Over a year ago

@caretaker was this an interview question or something you had to implement at work. Did you end up implementing the above approach? If not, what did you do?

Collectives™ on Stack Overflow

Modified Shortest path algorithm, forbidden paths

1 Answer 1

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related