Shortest path that visits all vertices in a directed complete weighted graph

0
votes

Given: complete directed weighted graph. All weights are positive. Is there any simple way (heuristics?) to find the shortest (in terms of weights) path that visits all vertices? Number of vertices is around 25. This problem seems to be close to Asymmetric Travelling Salesman, but I don't require this path to be the cycle.

1
algorithmmatlabgraph
Read Hamiltonion path. – Autonomous
Do the weights satisfy the triangle inequality? – Gene
Not necessary, but in most of the cases they do. I guess, I can assume that it is satisfied – Evgenii Nikitin

1 Answers

2
votes

I would recommend K-shortest path approach:

http://www.mathworks.com/matlabcentral/fileexchange/32513-k-shortest-path-yen-s-algorithm

I think this is your best bet... Here is an example: lets say you have 8 nodes and need to get from node 1 to node 8 in the shortest path possible. Let's assume all nodes are connected to each other (i.e., node 1 is connected to node 2:8, and so on). You will have to generate the "cost matrix" based on your problem. 

costMatrix = rand(8);
[shortestPath, cost] = dijkstra(costMatrix,1,8);

% Alternatively, return the 10 shortest paths from point 1 to 8:
[shortestPaths, costs] = kShortestPath(costMatrix,1,8,10);

Position (i,j) in the cost matrix is the cost of traveling from node i to node j. If costMatrix(i,j) = inf; there is no connection between node i and node j.

After looking into hidden markov models, I found a number of potential problems - the emission matrix would be difficult to define and you can run into problems where you would enter a "state" two or more times during a single "route." With the k-shortest path, this error doesn't occur.