Travelling Salesperson

I'm taking an AI course this year and we have started to study some algorithms which will involve graph and tree traversals. For starters, we were given a very stripped down version of the travelling salesperson algorithm to work out in C/C++/C#/etc. The graph is undirected and each city can be visited only once, the salesperson must start from A, visit all cities and come back to city A. The values along the paths are the cost associated to the travel to each city. The task was to devise an algorithm which would compute all the possible paths and would give the total cost of each route. I devised a generic solution (it still can't do city repetitions and it assumes that all cities are to visited). The first algorithm was aimed at solving the problem at hand and was a quick and dirty solution to get the job done. It wasn't thread-safe and it used fixed-size data structures. The output was as follows:

ABCDEA - Cost: 940
ABCEDA - Cost: 920
ABDCEA - Cost: 920
ABDECA - Cost: 995
ABECDA - Cost: 875
ABEDCA - Cost: 970
ACBDEA - Cost: 975
ACBEDA - Cost: 930
ACDBEA - Cost: 930
ACDEBA - Cost: 970
ACEBDA - Cost: 910
ACEDBA - Cost: 995
ADBCEA - Cost: 880
ADBECA - Cost: 910
ADCBEA - Cost: 855
ADCEBA - Cost: 875
ADEBCA - Cost: 930
ADECBA - Cost: 920
AEBCDA - Cost: 855
AEBDCA - Cost: 930
AECBDA - Cost: 880
AECDBA - Cost: 920
AEDBCA - Cost: 975
AEDCBA - Cost: 940
Smallest Cost: 855

After that I redesigned the solution to be thread-safe and more organized with lesser hacks. I still have to incorporate a bunch of features. Here is what the header of tsp3.cpp reads:

// TODO:
// MUST VISIT: allow user to Nodes.mustvisit (char) for nodes that MUST be in the solution
// ALLOW REPEAT: a flag which tells us if cities can be revisited to find the most optimal solution
// TRAVEL: Nodes.Travel(src,dest) and take into account MUST VISIT and ALLOW REPEAT and give possible solutions

The solution I designed inherently supported directed and undirected graphs so that is one less thing on the TODO list.