An algorithm question for calculating shotest path
Author
Hi there,
For the following unidirectional (one-direct only) pairs:
A-B; G-H; B-D; D-G; H-K; K-D;
The shortest path between A and D is: A-B-D, but none between A and H. Any hint on how to design such an algorithm using C++ or other programming language ?
Thanks in advance.
Robert
The classic algorithm is Dijkstra's, and in games programming A* is very popular.
[edit]Do you mean there is no path from H to A? Because there is an A-H path in your example ;)
[edit]Do you mean there is no path from H to A? Because there is an A-H path in your example ;)
Author
Yes, there IS a A to H path in my example if the path between each pair is bidirectional, but there is no such a path ("none") when only considering unidirectional path: A-B means A to B, but NOT B to A. To simplify, I start with only considering unidirectional path.
Quote:Yes, there IS a A to H path in my example if the path between each pair is bidirectional, but there is no such a path ("none") when only considering unidirectional path: A-B means A to B, but NOT B to A. To simplify, I start with only considering unidirectional path.It seems to me that there is a path between A and H: A-B-D-G-H.
What am I missing?
Usually you describe edges/links/neighbours in a graph.
And in a unidirectional graph you simply don't create an edge to a nieghbouring node if that edge isn't available.
And in a unidirectional graph you simply don't create an edge to a nieghbouring node if that edge isn't available.
Standard pathfinding algorithms apply, except that you'd have an additional check to see if you can visit a neighbouring node or not (e.g. is it an incoming or outgoing link). Which means you'll have to store the direction of a link somehow - possibly by only storing 'outgoing' links.
Note that there is a path between A and H, as others already pointed out, but it's one direction only, so to be specific, you'd have to say that there's no path from H to A, only one from A to H. If you want to know if two points have a path to each other you'd have to find a path twice, one for each direction, because there's no guarantee that the paths will be the same.
Note that there is a path between A and H, as others already pointed out, but it's one direction only, so to be specific, you'd have to say that there's no path from H to A, only one from A to H. If you want to know if two points have a path to each other you'd have to find a path twice, one for each direction, because there's no guarantee that the paths will be the same.
Use Floyd-Warshall algorithm for all pairs.
For single-source shortest paths Dijkstra should work. The "no path" will simply result in some nodes left with initial INFINITY value, meaning they can't be reached.
For single-source shortest paths Dijkstra should work. The "no path" will simply result in some nodes left with initial INFINITY value, meaning they can't be reached.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
