CODEWITHSUNDEEP
c#algorithm
Nikita K
Nikita K

Reputation: 135

Shortest route between locations algorithm

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.

Upvotes: 1

Views: 2424

Answers (1)

Codor
Codor

Reputation: 17605

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.

Upvotes: 5

Related Questions