Constrained shortest path in LEMON C++

Question

I have a simple example of graph:

ListDigraph g;
ListDigraph::ArcMap<int> length(g);
ListDigraph::ArcMap<string> color(g);
build_graph(g, length, color); // function building the graph

The map length contains the weights of the graph, while the map color contains the color of the arcs.

I would like to solve shortest path using Dijkstra, but in a constrained way: for example, I want to avoid two consecutive red arcs in the path.

Dijkstra in LEMON can be called simply by:

Dijkstra<ListDigraph, ListDigraph::ArcMap> dijkstra_test(g,length);
dijkstra_test.run(s);

How can I add a constrain the shortest path computation ?

Answer 1

Use a modified BFS to search through all paths between start and end. Stop the search when a path is found that meets the constraints.

• Start by putting the start vertex on top of a stack.
• LOOP
  • IF stack empty
    • Output 'NO PATH' and STOP
  • Take the top vertex off the stack and add it to the visited list and the current path
  • Add adjacent vertices which aren't in the visited list to the top of the stack.
  • IF the destination has been reached
    • IF current path meets constraints
      • Output path and STOP
    • Add current path to output
    • Backtrack along path to vertex adjacent to vertex on top of stack, marking vertices as unvisited

Notice that this does not give the shortest path that meets the constraints. If you need that, then the search must continue until exhaustion, replacing the path to be output whenever a shorter one is found that meets the constraints.

Answer 2

Use a product construction. See https://cs.stackexchange.com/q/118977/755. Construct a new graph, where you double the number of vertices; for each vertex v in the original graph, you have v0 (indicating that you entered v via an arc that was not red) and v1 (indicating that you entered v via an arc that was red). You should be able to fill in the edges in this graph. Then, use any algorithm for reachability in this graph, e.g., DFS, BFS, etc.