Re: [Tcllib-devel] ping gsoc graph work ...

[Michał A. <ant...@gm...>]

Just to avoid confusion:

>>About TSP:

>>One thing this would depend on is whether the route found is required to
be a cycle, or can visit vertices more than once.

>>I would stick to definition of the problem, which says that we are looking
for path (with minimal cost) which visits each node >>exactly once, and ends
in the starting node.

I meant it considering complete graph, on which algorithm is working. For
graphs that are not complete it's possible that algorithm will pick an edge
that was not in that graph before ( generally, it shouldn't ... that's why
we add huge weights on additional edges ) and there will be a jump from node
to node with unexisting arc. That's why at the end those jumps have to be
changed into shortest paths between those nodes using existing edges ( total
cost can't be worser -> metric ). In that case we have some nodes occur more
than once in the final solution.

Best Regards,
Michał Antoniewski