Implement the traveling salesperson algorithm on graphs 4 and 5. Both graph files are in the same format as the previous assignment, a list of nodes with a single node per line, a blank line, and then the list of edges in the form A B X, where X is the edge cost. Both graphs are connected (reminder that means when you read in an edge (A B X) from the file, you must also add edge (B A X)). (Graph 4 was constructed via scripts using n to separate each line, so it will come up as a long line of text if opened in regular notepad.) You may use your graph class from assignment #2 if you wish. I highly recommend testing your program on the graph contained in graph5.txt first as it is the smaller of the two graphs.
To solve the traveling salesperson problem, you must find the lowest cost simple cycle in the graph which traverses every node. To brute force this problem, that means you must check every each cycle that traverses each node in the graph (reminder that it does not matter which node you start a cycle from, as a cycle can begin with any node contained within it). Extra credit will be given to assignments which do not need to traverse all possible cycles but are still able to arrive at the optimal solution. Your implementation will need to be able to handle graphs of up to 15 nodes (we will test solutions with optimization heuristics on different graphs), and provide output of the shortest cost simple cycle, along with its cost.
If the graph is the one below, the output should be in the following form:
The graph has 4 nodes
The shortest cost cycle is: A B C D A
The cost of the above cycle is 4
A
B
C
D
A B 1
A C 29
A D 1
B C 1
B D 100
C D 1