Menu
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?
428
Dijkstra's algorithm is efficient because it only works with a smaller subset of the possible paths through a graph (i.e., it doesn't have to read through all of your data). After each node is solved, the shortest path from the start node is known and all subsequent paths build upon that knowledge.
The graph has two types of traversal algorithms. These are called the Breadth First Search and Depth First Search.
The only difference between a graph and a tree is cycle. A graph may contain cycles, a tree cannot. So when you're going to implement a search algorithm on a tree, you don't need to consider the existence of cycles, but when working with an arbitrary graph, you'll need to consider them.
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.
176
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.
24
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
