<p>I'm looking for a graph algorithm with some unusual properties.</p>

<p>Each edge in the graph is either an "up" edge or a "down" edge.</p>

<p>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.</p>

<p>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</p>

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

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.