Jump to content
  • Advertisement
Sign in to follow this  
Robert007

An algorithm question for calculating shotest path

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

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
Share on other sites
Advertisement
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 ;)

Share this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!