Travelling Salesman Problem

Problem

Calculate the minimum path to visit all N cities, starting and finish at the salesman's home. N cities means (N-2)! candidates. It's a NP problem.

Solution

Dijkstra's:

  1. Send out explorer's to all adjacent nodes.
  2. If the explorer is the first to reach that node, or the route it took was shorter than the previous explorer, send new explorers out to all adjacent nodes
  3. If the explorer is not the first to reach that node, compare the length of the route it took to get there. If it's shorter than the previous explorer's route, send out new explorere
Note that it is not necessary to record the entire root to the node, just a pointer to the previous node on the route