Graph searching algorithm

Question

I'm looking for a graph algorithm with some unusual properties.

Each edge in the graph is either an "up" edge or a "down" edge.

A valid path can go an indefinite number of "up"'s followed by an indefinite number of "down"'s, or vice versa. However it cannot change direction more than once.

E.g., a valid path might be A "up" B "up" C "down" E "down" F an invalid path might be A "up" B "down" C "up" D

What is a good algorithm for finding the shortest valid path between two nodes? What about finding all of the equal length shortest paths?

Answer 1

Assuming you don't have any heuristics, a variation of dijkstra's algorithm should suffice pretty well. Every time you consider a new edge, store information about its "ancestors". Then, check for the invariant (only one direction change), and backtrack if it is violated.

The ancestors here are all the edges that were traversed to get to the current node, along the shortest path. One good way to store the ancestor information would be as a pair of numbers. If U is up, and D is down, a particular edge's ancestors could be UUUDDDD, which would be the pair 3, 4. You will not need a third number, because of the invariant.

Since we have used dijkstra's algorithm, finding multiple shortest paths is already taken care of.

Answer 2

Maybe you can transform your graph into a normal directed graph and then use existing algorithms.

One way would be to split the graph into two graphs, one with all the up edges and one with all the down edges and with directed edges between all the nodes on graph one and the corresponding node on graph two.

First solve for starting in graph one and ending in graph two and then the other way around, then check the shortest solution.

Answer 3

One would think your standard BFS should work here. Whenever you add a node to the open list, you can wrap it into a struct that holds which direction it is using (up or down) and a boolean flag indicating whether it has switched directions yet. These can be used to determine which outgoing edges from that node are valid.

To find all shortest paths of equal length, include the number of edges traversed so far in your struct. When you find your first shortest path, make a note of the path length and stop adding nodes to the open list. Keep going through the remaining nodes on the list until you have checked all paths of the current length, then stop.

Answer 4

A* with a specially crafted cost (G score) and heuristic (H score) function can handle it.

For the cost you could keep track of the number of direction changes in the path and add infinite cost on the second change (ie. cut off the search for those branches).

The heuristic takes some more thought, especially when you want to keep the heuristic admissible (never overestimates minimum distance to goal) and monotonic. (Only way to guarantee A* finds an optimal solution.)

Maybe there is more information about the domain available to create the heuristic? (ie. x,y coordinates of the nodes in the graph?)

Of course, depending on the size of the graph you want to solve, you could first try simpler algorithms like breadth first search or Dijkstra's algorithm: basically every search algorithm will do, and for every one you will need a cost function (or similar) anyway.

Answer 5

I wish I could accept more than one answer here.

Answer 6

If you have a standard graph search function, say Graph.shortest(from, to) in a library, you can loop and minimize, in C#/pseudocode:

[ (fst.shortest(A, C) + nxt.shortest(C, B)) 
    for C in nodes , (fst, nxt) in [(up, down), (down, up)] ].reduce(min)

If you need to remember the minimum path/paths and it so happens that your standard function returns you the data, you could also pronounce

[ [fst, nxt, C, fst.shortest(A, C), nxt.shortest(C,B)]
    for C in nodes , (fst, nxt) in [(up, down), (down, up)] ].reduce(myMin)

where myMin should compare two [fst, nxt, C, AC, BD] tuples and leave the one that has lower distance, or both and assuming reduce is a smart function.

This has some memory overhead if our graphs are large and don't use memory at all (which is possible if they are generated dynamically), but not really any speed overhead, imho.