An algorithm question for calculating shotest path

This topic is 3349 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

Recommended Posts

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

Share on other sites
The classic algorithm is Dijkstra's, and in games programming A* is very popular.

Do you mean there is no path from H to A? Because there is an A-H path in your example ;)

Share on other sites
What do you mean by 'none between A and H'?

Share on other sites
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.

Share on other sites
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?

Share on other sites
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.

Share on other sites
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.

Share on other sites
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.

1. 1
2. 2
Rutin
16
3. 3
4. 4
5. 5

• 26
• 11
• 9
• 9
• 11
• Forum Statistics

• Total Topics
633703
• Total Posts
3013454
×