Find the shortest path in a graph that visits certain nodes

Question

I have an undirected graph with about 100 nodes and about 200 edges. One node is marked “start”, one is “end”, and there are about a dozen marked “mustpass”.

I need to find the shortest path through this graph, which starts with "start", ends with "end", and goes through all the nodes of "mustpass" (in any order).

( http://3e.org/local/maize-graph.png / http://3e.org/local/maize-graph.dot.txt is the graph in question - it is a corn maze in Lancaster, PA)

Answer 1

Everyone else, comparing this to the Traveling Salesman problem, probably did not carefully read your question. In TSP, the task is to find the shortest loop that visits all the vertices (Hamiltonian loop) - this corresponds to the fact that each node is marked as mandatory.

In your case, given that you only have about a dozen labeled "mustpass", and given that 12! (479001600), you can just try all permutations of only the mustpass nodes and see the shortest path from start to end that visits the mustpass nodes in that order - it’s just being a concatenation of the shortest paths between every two consecutive nodes in on this list.

In other words, first find the shortest distance between each pair of vertices (you can use the Dijkstra algorithm or others, but with such small numbers (100 nodes), even the simplest Floyd-Warsall algorithm in the code will start in time). Then, as soon as you get this in the table, try all the permutations of your "required" nodes, and the rest.

Something like that:

//Precomputation: Find all pairs shortest paths, eg using Floyd-Warshall n = number of nodes for i=1 to n: for j=1 to n: d[i][j]=INF for k=1 to n: for i=1 to n: for j=1 to n: d[i][j] = min(d[i][j], d[i][k] + d[k][j]) //That *really* gives the shortest distance between every pair of nodes! :-) //Now try all permutations shortest = INF for each permutation a[1],a[2],...a[k] of the 'mustpass' nodes: shortest = min(shortest, d['start'][a[1]]+d[a[1]][a[2]]+...+d[a[k]]['end']) print shortest 

(Of course, this is not real code, and if you need the actual path, you will need to keep track of which permutation gives the shortest distance, and also that all paired shortest paths, but you get the idea.)

It will work in a few seconds in any reasonable language :)
[If you have n nodes and k 'mustpass' nodes, its runtime is O (n ³ ) for the Floyd-Warshall part, and O (k! N) for the entire part of the permutations and 100 ^ 3 + (12!) ( 100) is practically peanuts unless you have really restrictive restrictions.]

Answer 2

run the Jikstra algorithm to find the shortest paths between all critical nodes (start, end and obligatory pass), then the depth - the first bypass should tell you the shortest path through the resulting subgraph, which affects all nodes, starts ... mustpasses ... end

Answer 3

Actually, the problem you posted looks like a traveling salesman, but I think it is closer to the simple problem of finding the way. Instead of visiting each node, you just need to visit a specific set of nodes in the shortest possible time (distance).

The reason for this is that, unlike the traveling salesman problem, the corn labyrinth will not allow you to move directly from any point to any other point on the map without passing through other nodes to get there.

I would recommend A * pathfinding as a method to consider. You install this by deciding which nodes have access to which other nodes directly, and what is the "cost" of each hop from a particular node. In this case, it seems that each “jump” may have the same cost, since your nodes look relatively close to each other. A * can use this information to find the cheapest way between any two points. Since you need to get from point A to point B and visit about 12 gaps, even a brute force approach using path finding will not hurt at all.

Just an alternative to consider. It looks wonderful, like a salesman problem, and these are good reading papers, but take a closer look and you will see that these are just superfluous things. ^ _ ^ It comes from the mind of a video game programmer who used to do these things.

Answer 4

These are two problems ... Stephen Low pointed out this, but did not give sufficient respect for the second half of the problem.

First you must find the shortest paths between all of your critical nodes (start, end, mustpass). Once these paths are discovered, you can build a simplified graph where each edge in a new graph represents the path from one critical node to another in the original graph. There are many path search algorithms that you can use to find the shortest path here.

However, if you have this new schedule, you have a problem with Traveling Salesperson (well, almost ... there is no need to return to the starting point). Any of the posts related to this mentioned above will apply.

Answer 5

Given that the number of nodes and edges is relatively small, you can calculate all the possible paths and take the shortest.

This is generally known as the traveling salesman problem and has non-deterministic polynomial runtimes, regardless of which algorithm you use.

http://en.wikipedia.org/wiki/Traveling_salesman_problem

Answer 6

Andrew Top has the right idea:

1) Jikstra Algorithm 2) Some TSP heuristics.

I recommend the Lin-Kernighan heuristic: this is one of the best known for any NP complete problem. The only thing to remember is that after you expand the graph again after step 2, you may have loops in the extended path, so you should bypass their short circuit (look at the degree of the vertices along your path).

In fact, I'm not sure how well this solution will be relatively optimal. There are probably some pathological cases associated with a short circuit. In the end, this problem looks LOT like a Steiner Tree: http://en.wikipedia.org/wiki/Steiner_tree , and you definitely can’t get closer to the Steiner Tree by simply cutting your schedule and, for example, launching Kruskal.

Answer 7

It would be nice to tell us if the algorithm should work in about a second, day, week or so :) If the week is ok and it at once, you can write the software in a few hours and overdo it. But if it is built into the user interface and needs to be calculated many times a day ... another problem, I think.

Answer 8

This is not a TSP problem, not NP-hard, because the original question does not require bandwidth nodes to be visited only once. This makes the answer much easier than just brute force after compiling a list of shortest paths between all nodes with bandwidth through the Dijkstra algorithm. Maybe the best way to go, but a simple one would be to just work backwards with the binary tree. Imagine a list of nodes [start, a, b, c, end]. Summarize simple distances [start-> a-> b-> c-> end], this is your new target distance to beat. Now try [start-> a-> c-> b-> end], and if it’s better to set it as a target (and remember that it came from this node template). Work backward on permutations:

• [Start-> a-> b-> c-> end]
• [Start-> a-> C-> b-> end]
• [Start-> b-> a-> C-> end]
• [Start-> b-> c-> a-> end]
• [Start-> C-> a-> b-> end]
• [Start-> C-> b-> a-> end]

One of them will be the shortest.

(where are the nodes "visited several times", if there are any? They are simply hidden at the initialization stage of the shortest path. The shortest path between a and b may contain c or even an endpoint. you need to take care)

Answer 9

How about using brute force on dozens of “need to visit” nodes. You can easily cover all possible combinations of 12 nodes, and this leaves you with an optimal pattern that you can follow to cover them.

Now your problem is simplified to find the best routes from the beginning of the node to the pattern that you then follow until you cover them, and then find the route from this to the end.

The final path consists of:

start → path to the path * → the circuit should visit the nodes → path to the end * → end

You will find the paths marked with a *, like this

Do an A * search from the beginning of the node to each point in the diagram for each of them; search A * from the next and previous node in the diagram to the end (because you can follow the circle in any direction) As a result, you have many search paths, and you You can choose the one that has the lowest cost.

There are many opportunities for optimization by caching search, but I think it will create good solutions.

It is not suitable for finding the best solution anywhere, because it can lead to the fact that you should visit the search scheme.

Answer 10

One thing that is not mentioned anywhere is whether it is possible to visit the same peak more than once in a journey. Most of the answers here suggest that you can visit the same edge several times, but my question asks a question (a path should not visit the same peak more than once!) It is not good to visit the same peak twice.

Thus, the brute force approach will still apply, but you will have to remove the vertices that were already used when trying to calculate each subset of the path.