# methods for solving this simple routing problem

In my transport geography class, we were asked to do a "best guess" on the route which does the following on this graph:

1. Starts at A
2. Visits each node
3. Returns to A
4. minimizes distance.

I wrote up program which calculated all of the five step paths that started from A, visited every node, and returned to A. I then calculated the cost of these paths.

How would other people solve this?

My teacher gave us a "hint" that we should read about Dijkstra's algorithm, but I couldn't see how to apply that to solve this particular problem. My solution would fall apart pretty quickly as the number of steps or nodes increased.

-
Your program was lucky, because it's not guaranteed to get the best answer. For instance, if all the edges at E had costs of 1 (instead of 3,4,5,3), your program's solution would be markedly inferior to the optimum (with a cost of 8). – whuber Sep 7 '11 at 14:09
@Whuber I was hoping that you would share some of your math knowledge here ;) I considered doing a range of steps, maybe between 5 and 10, to guard against that, recognizing it wouldn't provide a guarantee. Not sure how to provide that guarantee, though. – canisrufus Sep 7 '11 at 14:22
A brute force solution uses recursion to solve a slightly more general problem: get from node 'v' to node 'w' while visiting a specified set of additional nodes. Thus, to visit all nodes starting at 'a', look at the solutions that start at 'v', end at 'a', and visit all other nodes, for the cases 'v' = 'b', 'v' = 'd', and 'v' = 'e'. Add the costs 3, 7, and 3 to those solutions, respectively. Pick the smallest cost. – whuber Sep 7 '11 at 15:54
@whuber: That's very clear, as far as it goes. I think I can work out what the recursion would look like. I'd like to accept your response, but it's not in the "answers" section.. – canisrufus Sep 8 '11 at 12:26

I'd advise you to look up, research, the travelling salesman problem for some soutions.

Here's a link to a way to formulate a solution. In short, this is a tricky subject to get into/understand:

TSP solutions

-
"It's complicated." ;) Good link, though. I spent some time researching TSP, but didn't find anything as useful as that. – canisrufus Sep 7 '11 at 13:57

Imho, "Dijkstra" is not a good hint. What you are looking at is the so-called "Travelling salesman problem".

Given a list of cities and their pairwise distances, the task is to find a shortest possible tour that visits each city exactly once.

Since a brute-force approach performs with O(n!), they reach their limit pretty fast (WP says 20 nodes is already the limit).

-
Thanks! I didn't find Dijkstra to be especially useful, though another student claimed to. Do TSPs also include the part where you have to return to origin? I didn't see that mentioned when I looked them up yesterday, although, of course salespeople need to drive home, too... – canisrufus Sep 7 '11 at 14:05
@canis You are correct: the Dijkstra algorithm is useless for this problem. Note that your problem as stated is not the TSP, because you have not indicated that each node must be visited exactly once, only that it must be visited at some point in the route. – whuber Sep 7 '11 at 14:14
In all fairness Whuber, I think that's more of an over simplification of the problem. I actually do think the OP has been tasked with the TSP; I got the same questions in my dfegree, and I believe most people will/do – Hairy Sep 8 '11 at 6:25