在图中找到访问某些节点的最短路径 [英] Find the shortest path in a graph which visits certain nodes

问题描述

我有一个大约有 100 个节点和大约 200 条边的无向图.一个节点标记为开始"，一个标记为结束"，大约有十几个标记为必须通过".

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

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

解决方案

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

就您而言，鉴于您只有大约 12 个标记为必须通过"，并且有 12 个！相当小(479001600)，您可以简单地尝试仅mustpass"节点的所有排列，并查看从start"到end"的最短路径，该路径按该顺序访问mustpass"节点——它只会是该列表中每两个连续节点之间最短路径的串联.

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

像这样:

//预计算:找出所有对的最短路径，例如使用 Floyd-Warshalln = 节点数对于 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对于必须通过"节点的每个排列 a[1],a[2],...a[k]:最短 = 分钟(最短，d['start'][a[1]]+d[a[1]][a[2]]+...+d[a[k]]['end'])打印最短

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

它在任何合理的语言上最多只运行几秒钟:)
[如果您有 n 个节点和 k 个必须通过"节点，则 Floyd-Warshall 部分的运行时间为 O(n³)，所有排列部分的运行时间为 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(n³) 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.]

这篇关于在图中找到访问某些节点的最短路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！