algorithm - 在访问某些节点的图中找到最短路径

Question

我有一个无向图，有大约 100 个节点和大约 200 条边。一个节点标记为“开始”，一个节点标记为“结束”，还有大约一打标记为“必须通过”。

我需要找到通过此图的最短路径，该路径从“开始”开始，在“结束”结束，并通过所有“必须通过”节点(以任何顺序)。

(http://3e.org/local/maize-graph.png/http://3e.org/local/maize-graph.dot.txt 是有问题的图表 - 它代表宾夕法尼亚州兰开斯特的 Jade 米迷宫)

Answer 1

将此与旅行商问题进行比较的其他人可能没有仔细阅读您的问题。在 TSP 中，目标是找到访问所有 顶点的最短循环(哈密顿循环)——它对应于标记为“必须通过”的每个节点。 p>

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

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

像这样:

//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³)，对于所有排列部分是 O(k!n)，并且100^3+(12!)(100) 实际上是花生，除非你有一些非常严格的限制。]