其他将此与“旅行推销员问题”相比较的人，可能还没有仔细阅读您的问题。在TSP中，目标是找到访问 所有 顶点的最短周期（哈密顿周期）-它对应于将 每个
节点标记为“必须通过”。

在您的情况下，假设您只有大约十二个标记为“必须通过”的标签，并且有十二个标签！相当小（479001600），您可以仅尝试“必须通过”节点的所有排列，并查看从“开始”到“结束”的最短路径，以该顺序访问“必须通过”节点-
是该列表中每两个连续节点之间的最短路径的串联。

换句话说，首先要找到每对顶点之间的最短距离（您可以使用Dijkstra的算法或其他方法，但是使用那些较小的数（100个节点），即使最简单的代码Floyd-
Warshall算法也会及时运行）。然后，将其放在表中后，请尝试“必须通过”节点的所有排列，然后尝试其余的排列。

像这样：

//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

（当然，这不是真正的代码，如果您想要实际的路径，则必须跟踪哪个排列给出最短的距离以及所有对最短的路径是什么，但是您明白了。）

它可以在任何合理的语言下最多运行几秒钟：)
[如果您有n个节点和k个“必须通过”节点，则对于Floyd-Warshall部分，其运行时间为O（n 3），而O（k！n
）的所有排列部分，除非您有一些严格的限制条件，否则100 ^ 3 +（12！）（100）实际上是花生。]