Shortest path in graph without repetitions

user_10964215 0
Viewed 92

I have a directed graph that every node contain a letter and every edge has weight. I want to find the shortest path from a start node to an end node, that doesn't have letters showing not in sequence and has all the letters in it. For example:

I have those nodes: 1 - start node, 2- end node, 3 - 'A' letter, 4 - 'B' letter, 5 - 'B' letter, 6 - 'A' letter, 7 - 'B' letter.
And the edges are: 1 -> 3, 1 -> 4, 3 -> 5, 4 -> 5, 5 -> 6, 5-> 7, 6 -> 2, 7 -> 2.

the graph looks like this: enter image description here

The only valid paths for me are:

1 -> 3 -> 5 -> 7 -> 2 ('ABB'), 1 -> 4 -> 5 -> 6 -> 2 ('BBA').

I want to get the option of 'BBA' because it is the shortest. If I'll try using dijkstra, when i get to node number 6, my path will go through nodes number 3 and 5. Then i will set the weight of the edge (5 -> 6) to be Infinity for this path so it won't take this path. But, because it already got that the shortest path to node number 5 is through node number 3, it will choose the path 'ABB'. How can i get the correct path?

edit: what I want to find is a path, that the same letter can only be visited in 1 group. I mean, if I visit an 'A' group already and then went to 'B' group, i can't travel to another 'A' again. I can travel like this:

A->A->C->B->B
dijkstra algorithm
1 Answers

Constraints

Ok, I believe the two constraints are as follows:

  1. The path must contain every letter in the alphabet at least once, and
  2. The entire path must either visit nodes in alphabetical order OR in reverse alphabetical order.

And I believe the alphabet can be substantially bigger, e.g. A-Z.

So first, let's just solve it for alphabetical order. If we can do that, then we only need to do the equivalent algorithm for reverse alphabetical order.

Modified Graph

So we modify the graph to have the following rules:

  • Each node N's outgoing edges can only connect to a node with the same letter or the letter that immediately follows (e.g. an "A" node can only send you to an "A" node or a "B" node, never a "C" node, "D" node, etc), otherwise we could visit nodes in non-alphabetical order and / or skip a letter in the path.
  • The start node's outgoing edges can only connect to a node with the first letter of the alphabet (e.g. an "A" node), otherwise we could not include "A" in our entire alphabetical path.
  • The end node's ingoing edges can only come from nodes with the last letter of the alphabet (e.g. a "B" node in your example), otherwise we could not include the last letter in our entire alphabetical path.

So in the above graph, we only keep the following edges for the alphabetical graph: 1 -> 3, 3 -> 5, 5 -> 7, and 7 -> 2.

Similarly, for the reverse alphabetical graph we only keep the following edges: 1 -> 4, 4 -> 5, 5 -> 6, 5 -> 7, 6 -> 2. Note that node 7 would no longer have any outgoing edge.

Once you've done this, any path (in the modified graph) from start to end must be a valid path, because:

  1. The path must contain every letter in the alphabet at least once (no letters were skipped AND the first node was the first letter AND and the last node was the last letter), and
  2. The entire path visited nodes in alphabetical order (since each individual edge was alphabetical).

Given this, regular Dijkstra should work perfectly on this modified graph.

Final Framework

Given the above, your entire algorithm is as follows:

  1. Create the two modified graphs: one alphabetical, one reverse alphabetical.
  2. Run Dijkstra on each modified graph.
  3. Pick the best solution between the two.
user_89813450
Related