1

I need to find the shortest route between 2 locations. To elaborate:

I am given an excel file that contains 3 columns: city1, city2, distance between them. The condition is that if there is a route between city1 and city2, then there's a route between city2 and city1.

The file has multiple rows and the task is to read it and determine the shortest path in terms of distance between city X and city Y. However, within the table the path may look like:

...

X, N, 100

X, M, 200

U, Y, 50

X, U, 20

...

I. e. there is no direct path from X to Y, and the answer to the question would be X -> U -> Y = 20 + 50 = 70, which is shortest distance. In this form, there may be numerous locations in between the asked for departure and arrival points.

The UI asks for departure, destination and outputs the shortest path between those.

I hope I explained it well enough to get the idea. I'm trying to solve this in C# but I am more looking for a general approach, an algorithm to solve this. I realize it might be somewhat related to the Travelling salesman problem, but I wasn't able to apply that.

Any direction / help / code samples appreciated.

Nikita K
  • 135
  • 1
  • 12
  • 1
    Take a look at A* perhaps? http://en.wikipedia.org/wiki/A*_search_algorithm – Golden Dragon Jan 13 '15 at 15:15
  • 6
    You want the [Shortest path problem](http://en.wikipedia.org/wiki/Shortest_path_problem), not the Travelling salesman problem. – Rawling Jan 13 '15 at 15:15
  • There is an *exponential* difference between a shortest path problem and the travelling salesman. Which is lucky for you. – Ant P Jan 13 '15 at 15:15

1 Answers1

5

The problem described is algorithmically easier than the Travelling Salesman problem, which is NP-hard. It is the Shortest Path problem, which can be solved efficiently with Dijkstra's algorithm. This algorithm requires the distances to be of nonnegative length, which seems to be the case for your context, as the edge weights are nonnegative.

Codor
  • 17,447
  • 9
  • 29
  • 56
  • 1
    No, my mistake. Dijkstra doesn't accept negative edges indeed. There is an [example here](http://stackoverflow.com/questions/6799172/negative-weights-using-dijkstras-algorithm). – Juan Lopes Jan 13 '15 at 15:31
  • 1
    Yes Dijkstra's is what you want. Here is an implementation in C# - http://www.c-sharpcorner.com/Blogs/15009/coding-for-dijkstras-algorithm.aspx – shaw2thefloor Jan 13 '15 at 15:32
  • @JuanLopes Thanks for the clarification. In fact, if negative cycles are permitted, the optimization problem is somewhat ill-defined as a path of arbitrarily small negative length might exist. – Codor Jan 13 '15 at 15:33
  • It's trivial to overcome negative lengths. You find the smallest one (the negative edge whose absolute value is the largest) and just subtract its length from all edges. So if the length of the smallest edge is (-100), you add 100 to all edges. You then sit back and run the algorithm. – Malt Jan 13 '15 at 16:16