Help with shortest path problem.

[jhender4880]

I have to write a program that uses the shortest path that starts at a "home" city and goes to 3 other cities and back "home" again. I have been reading for a few hours about a good way to solve this problem. It seems to be a variation of the traveling salesman problem. I have read about using the dijkstra algorithm but that seems too complicated for this problem. I am using the cities Atlanta, New York, Chicago, and Los Angeles (Atlanta being "home") and want to use the actual miles between the cities in the program. My question is what would be the best way to tackle this problem? I am not asking for the code just how to get started. I am new to Java but am ok with C++.

I have made an undirectional graph with the miles between cities but I am unsure about where to go from here.

[Slavi]

I think dijkstra is the way to go, what is your code so far?

[JamesCherrill]

Just 3 cities - you can search all possible paths. TSP is only interesting when you get many cities.

[jhender4880]

I have no code written yet. I am just trying to decide what is the best approach. I have looked at a lot of Dijkstra examples but none that I have seen come back to the "home" city.

[jhender4880]

Search all possible paths to find the shortest route to all 3 and back again? Which algorithim would you suggest for that? I have only been exposed to Java for 1 week.

[Slavi]

First I think you need to understand how to make a graph of them and to find how reach from home position to goal position. Take a look at Breadt first search and if you have any experience with recursion take a look at Deep first search. If you understand those, implementing dijkstra for the shortest path would take you no time :)

[jhender4880]

Ok, Thanks. I was thinking since it's only 5 cities total and all I really want to do is find the route that takes me the least amount of miles, couldn't I just add up the mileage for every possible path and whichever is the lowest is the shortest path?

I have made a graph of the cities with the mileage between each city. My home and destination are the same place. I will look at the Breadth first search.

[Slavi]

It really depends on what exactly your assignment is, but if you have to make an algorithm then the algorithm should find it for you. The way I understand is you have the cities with distance between them. You know the source city and the distance from it and the connecting cities. What your algorithm should do is check which cities you have connection to and how much is the distance to them. Pick the shortest distance and set the city you just travelled to as your new source. Repeat until source is destination, is this what it has to do?

[jhender4880]

That's correct but if the program went with the shortest path first every time then the actual miles traveled would be longer than if it went to the second shortest first then the shortest first after that. The cities are Atlanta (home), Chicago, New York, Minneapolis, and Los Angeles. If the program went shortest path first the path would be Atlanta, to Chicago, to Minneapolis, to New York, then back to Atlanta. If the program took the second shortest path first it'd be Atlanta, to New York to Chicago, to Minneapolis, to Los Angeles, the back to Atlanta. This second path would actually save a person driving over 1K miles than going with the shortest path first always. That's where I am having a real problem, the shortest path first won't end up with the overall shortest route.