3

I am trying to find the shortest possible path that visits every node through a graph (a node may be visited more than once, the solution may pick any node as the starting node.). The graph is directed, meaning that being able to travel from node A to node B does not mean one can travel from node B to node A. All distances between nodes are equal. I was able to code a brute force search that found a path of only 27 nodes when I had 27 nodes and each node had a connection to 2 or 1 other node. However, the actual problem that I am trying to solve consists of 256 nodes, with each node connecting to either 4 or 3 other nodes. The brute force algorithm that solved the 27 node graph can produce a 415 node solution (not optimal) within a few seconds, but using the processing power I have at my disposal takes about 6 hours to arrive at a 402 node solution.

What approach should I use to arrive at a solution that I can be certain is the optimal one? For example, use an optimizer algorithm to shorten a non-optimal solution? Or somehow adopt a brute force search that discards paths that are not optimal?

EDIT: (Copying a comment to an answer here to better clarify the question) To clarify, I am not saying that there is a Hamiltonian path and I need to find it, I am trying to find the shortest path in the 256 node graph that visits each node AT LEAST once. With the 27 node run, I was able to find a Hamiltonian path, which assured me that it was an optimal solution. I want to find a solution for the 256 node graph which is the shortest.

Improve this question
5
  • you want to find the shortest hamiltonian path? that is the traveling salesman problem
    – ratchet freak
    Aug 21, 2014 at 12:45
  • No, there is no assurance that there is a Hamiltonian path (a vertex may be visited more than once). I am trying to find the shortest path which satisfies the constraints that each node must be visited at least once. Distance between two nodes is equal to 1 if a path exists.
    – Boluc Papuccuoglu
    Aug 21, 2014 at 12:47
  • still a traveling salesman problem: add the missing edges with the shortest path between the 2 nodes and then fire a salesman solver at it.
    – ratchet freak
    Aug 21, 2014 at 12:50
  • @ratchetfreak, could you clarify that last comment a bit, and perhaps post it as an answer in an expanded form? It sounds promising, but I can't be sure because I don't understand what you are saying completely.
    – Boluc Papuccuoglu
    Aug 21, 2014 at 12:52
  • I just read more about the TSP, and one of the defining characteristics seems to be "that visits each city exactly once". In its current form, there is no constraint to visit each node once and also there is no guarantee that there exists a path that visits each node just once. Is there a way to transform my problem to TSP?
    – Boluc Papuccuoglu
    Aug 21, 2014 at 13:04

4 Answers 4

Reset to default
5

This is NP-hard. If you have a solution for this problem, then you can use it on a graph with all edge weights set to 1. Then the resulting path will have the same number of nodes as the graph if and only if there is a Hamiltonian path. Since determining the existence of a Hamiltonian path is NP-hard even without finding specific solutions, any solution to this problem is at least as hard.

Wikipedia page: http://en.wikipedia.org/wiki/Hamiltonian_path

Edit: You might want to look at approximate solutions, but I have little experience with those. The wiki page tells you a lot more than I can: http://en.wikipedia.org/wiki/Approximation_algorithm

Improve this answer
6
  • 1
    To clarify, I am not saying that there is a Hamiltonian path and I need to find it, I am trying to find the shortest path in the 256 node graph that visits each node AT LEAST once. With the 27 node run, I was able to find a Hamiltonian path, which assured me that it was an optimal solution. I want to find a solution for the 256 node graph which is the shortest.
    – Boluc Papuccuoglu
    Aug 21, 2014 at 12:48
  • Yes, but if such an algorithm exists it can be used to solve the Hamiltonian path existence problem as I described, which makes the problem you are working on NP-hard. I edited my answer slightly to make this more clear.
    – Joseph Pepper
    Aug 21, 2014 at 13:10
  • I am not saying that I need to find an algorithm for any graph that fits my description. I have a certain 256-node graph that I need to solve.
    – Boluc Papuccuoglu
    Aug 21, 2014 at 13:14
  • For a generic graph, there's not much you can do besides improved versions of brute force. More specific properties are necessary in order to tailor an algorithm to it.
    – Joseph Pepper
    Aug 21, 2014 at 13:18
  • For example, if you can identify a small number of nodes whose removal partitions the graph into several pieces, you can make an approximate solution by combining solutions to the different subgraphs and linking across the cut nodes. However, this is unlikely to be optimal.
    – Joseph Pepper
    Aug 21, 2014 at 13:21
2

If you want to visit all nodes then you have a variation of the traveling salesman problem.

given that you are allowed to visit a node multiple times you can generate any missing with a cost of the shortest path between the 2 nodes.

For example to get to V3 from V1 you need to pass V2, you can add an edge between V1 and V3 with a cost of (V1,V2)+(V2,V3).

This way you can solve it like a traveling salesman problem and the optimum route won't make any unnecessary trips. In the above example if the constructed edge is taken then the other visit to V2 is part of the optimum path otherwise the path through V2 would have been taken.

Improve this answer
1
  • Let's say that I add a 2-metric edge from V1 to V3 (which aren't connected in the original graph), passing through V2. Now, if the solution includes this edge, V2 does not actually need to be visited. However, the TSP solver WILL try to include V2 in its final solution, taking it away from the optimal. How can I prevent this?
    – Boluc Papuccuoglu
    Aug 21, 2014 at 14:16
0

From your description this seems to be a shortest path problem for a strongly connected directed graph. I'm not entirely sure whether you actually want a single-pair solution or an all-pair solution.

If the latter, it seems the Floyd-Warshall algorithm will do the job, with a complexity of O(n^3). Otherwise look here: http://en.wikipedia.org/wiki/Shortest_path_problem.

Improve this answer
-2

DFS can solve this problem. However, you must define an efficient evaluation function to prun the branch earlier. Some hints on the evaluation: - use greedy to find a good path first, this may be not a shortest path, but it allows to stop on other not good path - for each state, try the nearest state first - for each state, evaluation the minimum length to visit all state. The evaluation should be as tight as possible. This problem is more difficult but you can refer to my post on this problem here http://www.capacode.com/?p=650

Improve this answer
2
  • Posting a link to some code doesn't work to describe the algorithim used or the nature of the non-Hamiltonian path to solve it. Furthermore, external links may become dead.
    – user40980
    Mar 25, 2015 at 13:31
  • @MichaelT: thanks, I have revised and put more details
    – truongkhanh
    Mar 26, 2015 at 14:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.