我有一个无向图约100个​​节点和200的边缘。一个节点被标记为'开始'，一个是'端'，并有十几个标有​​mustpass。

我需要找到通过此图，在开始开始的最短路径，结束于结束，，并通过所有的mustpass节点传递（以任意顺序）。

（ http://3e.org/local/maize-graph.png /的Floyd-Warshall算法会在第一时间运行）。然后，一旦你有这样的一个表，试试你的'mustpass节点的所有排列，其余的。

事情是这样的：

  // precomputation：找到所有对最短路径，例如：用弗洛伊德 - 沃肖尔
节点的N =数
对于i = 1到n：对于j = 1到n：D [I] [j]的= INF
对于k = 1到n：
    对于i = 1到n：
        对于j = 1到n：
            D [I] [J] = MIN（D [I] [J]，D [I] [K] + D [k]的[J]。）
//那*真的*给每对节点之间的最短距离！ :-)

//现在尝试所有排列
最短= INF
为'mustpass'节点的每个排列一个[1]，A [2]，...一个[k]的：
    最短=分钟（最短，D ['开始'] [一个[1]] + D [一个[1]] [一个[2] + ... + D [一个[K]] [结束]）
打印最短
 

（当然，这不是真正的code，如果你想实际的路径，你就必须跟踪哪些置换给人的最短距离，也是全对的最短路径是什么，但是你得到了这个想法。）

这将至多几秒钟的任何合理的语言运行在:) [如果你有n个节点和k'mustpass节点，其运行时间为O（n 3 ）为弗洛伊德 - 沃肖尔部分和O（K！N）的所有排列的一部分， 100 ^ 3 +（12！）（100）实际上是花生，除非你有一些非常严格的限制。]

I have a undirected graph with about 100 nodes and about 200 edges. One node is labelled 'start', one is 'end', and there's about a dozen labelled 'mustpass'.

I need to find the shortest path through this graph that starts at 'start', ends at 'end', and passes through all of the 'mustpass' nodes (in any order).

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

Everyone else comparing this to the Travelling Salesman Problem probably hasn't read your question carefully. In TSP, the objective is to find the shortest cycle that visits all the vertices (a Hamiltonian cycle) -- it corresponds to having every node labelled 'mustpass'.

In your case, given that you have only about a dozen labelled 'mustpass', and given that 12! is rather small (479001600), you can simply try all permutations of only the 'mustpass' nodes, and look at the shortest path from 'start' to 'end' that visits the 'mustpass' nodes in that order -- it will simply be the concatenation of the shortest paths between every two consecutive nodes in that list.

In other words, first find the shortest distance between each pair of vertices (you can use Dijkstra's algorithm or others, but with those small numbers (100 nodes), even the simplest-to-code Floyd-Warshall algorithm will run in time). Then, once you have this in a table, try all permutations of your 'mustpass' nodes, and the rest.

Something like this:

//Precomputation: Find all pairs shortest paths, e.g. 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 that's not real code, and if you want the actual path you'll have to keep track of which permutation gives the shortest distance, and also what the all-pairs shortest paths are, but you get the idea.)

It will run in at most a few seconds on any reasonable language :) [If you have n nodes and k 'mustpass' nodes, its running time is O(n3) for the Floyd-Warshall part, and O(k!n) for the all permutations part, and 100^3+(12!)(100) is practically peanuts unless you have some really restrictive constraints.]