I am trying to learn some discrete math to solve my problem. I don't really know enough graph theory to find out how to solve this: Here is my problem: I have a COMPLETE digraph of N nodes, with N^2 weights W. I want to calculate the minimum path required to visit all nodes exactly once with the minimum cost. I think this is related to the Traveling Salesman Problem, but I dont know how exactly to modify it so that it can optimise for the fact that the graph is complete. I also don't understand how to solve it quickly. It is important that the algorithm execute quickly, for even though it doesn't have to be real-time, it shouldn't take forever (it will not happen every frame in a game I am making, but it may happen every couple of seconds or so) It may help optimisation to know that there will be relatively few items in the graph (I would be very surprised if the number of nodes ever got larger than a few hundred). I can also insert start and end dummy nodes if it improves the speed of the algorithm. can anyone help me figure this out?

hehe, holy crap.

I must have read that page a dozen times, but it works!

I decided on using a modified version of the Prim algorithm to do what I wanted.
I need a minimum spanning pathway instead of a tree, so I start with the first node, find the minimum path, connect the node, then repeat that for the ENDS of the tree (as opposed to every vertex) This means that the tree can only grow like a snake from either end. Then this becomes my minimum spanning path. Badass!

Thanks a ton

You should realize that the path you are finding is not necessarily minimal. The problem you described is the traveling salesman problem, so an approximation is necessary for efficiency.

Quote:Original post by Steve132
I have a COMPLETE digraph of N nodes, with N^2 weights W. I want to calculate the minimum path required to visit all nodes exactly once with the minimum cost.

You have a COMPLETE digraph, which means there is a directed edge from any node i to any other node j.

Also, you say all the weights are W, I don't see what your problem is!

Just pick any permutation of the nodes and you have a minimum cost path hitting all nodes exactly once.

If the weights could be different for different edges, you are probably looking at the "Asymmetric Travelling Salesman Problem". The Minimum Spanning Tree won't work.