Jump to content
  • Advertisement
Sign in to follow this  
Shantesh Patil

Best algorith for finding shortest path between say 2 cities

This topic is 4331 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

I have a table in access which has a list of cities and their corresponding horizontal and vertical coordinates and another table which contains on each row 2 cities which have a road connecting them and the distance between them my job initially is 2 find the shortest paths between all possible combinations of citiess and populate them in another table...this has to be done using c# so initially i would like to know which algorithm i should use for calculating the shortest path and also which data structures and other features of c# would be useful for the above process

Share this post


Link to post
Share on other sites
Advertisement
Dijkstra's algorithm guarentees the optimal result, but an A* search with a decent heuristic will be more efficient (and still guarentee correctness).

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
this is called the "travelling salesman problem".
just look it up (wikipedia or google)

Share this post


Link to post
Share on other sites
Quote:
Original post by Anonymous Poster
this is called the "travelling salesman problem".
just look it up (wikipedia or google)


That was my first thought too, but doesn't that refer to passing through each node/place only once?

Share this post


Link to post
Share on other sites
Is the graph data type the best way to store the values and manipulate them... graph does not seem to be present in framework 1.1 or at atleast the intellisense in visual studio 2003 does not prompt me.. it does however prompt me in the 2005 visual studio... am i wrong abt this

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Quote:
this is called the "travelling salesman problem".
just look it up (wikipedia or google)


No it's not.

Take your own advice and look it up in wikipedia or google.

Share this post


Link to post
Share on other sites
Quote:
Is the graph data type the best way to store the values and manipulate them... graph does not seem to be present in framework 1.1 or at atleast the intellisense in visual studio 2003 does not prompt me.. it does however prompt me in the 2005 visual studio... am i wrong abt this


A graph is indeed an appropriate data structure for this problem. However the .Net class libraries do not have a generic graph class AFAIK. So you've got to make the graph yourself, the simplest way to do this is just to have a node class that contains a list of the other nodes it is joined to along with distance information.

Share this post


Link to post
Share on other sites
Quote:
Original post by Cocalus
He's looking for a all pair shortest path algorithm.

Floyd-Warshall should work.

Quote:
Original post by Monder
A graph is indeed an appropriate data structure for this problem. However the .Net class libraries do not have a generic graph class AFAIK. So you've got to make the graph yourself, the simplest way to do this is just to have a node class that contains a list of the other nodes it is joined to along with distance information.

Quoted for emphasis. Don't be tempted by Dijkstra or A*.

Regards
Admiral

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!