Jump to content
• Advertisement

# Best algorith for finding shortest path between say 2 cities

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

##### Share on other sites
Advertisement
You are looking for http://en.wikipedia.org/wiki/Dijkstra's_algorithm

#### Share this post

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

##### Share on other sites
this is called the "travelling salesman problem".
just look it up (wikipedia or google)

#### Share this post

##### Share on other sites
He's looking for a all pair shortest path algorithm.

Floyd-Warshall should work.

#### Share this post

##### Share on other sites
Quote:
 Original post by Anonymous Posterthis 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

##### 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

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

##### 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

##### Share on other sites
Quote:
 Original post by CocalusHe's looking for a all pair shortest path algorithm. Floyd-Warshall should work.

Quote:
 Original post by MonderA 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

##### Share on other sites

• Advertisement
• Advertisement

• ### Popular Contributors

1. 1
2. 2
Rutin
19
3. 3
khawk
18
4. 4
5. 5
A4L
11
• Advertisement

• 9
• 12
• 16
• 26
• 10
• ### Forum Statistics

• Total Topics
633769
• Total Posts
3013754
×

## Important Information

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

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!