我有一个无向图,其中有大约 100 个节点和大约 200 条边。一个节点标记为“开始”,一个节点标记为“结束”,还有大约十几个标记为“必须通过”。我需要找到通过的最短路径...
我有一个无向图,其中有大约 100 个节点和大约 200 条边。一个节点标记为“开始”,一个节点标记为“结束”,还有大约十几个标记为“必须通过”。
我需要找到该图中最短的路径,该路径始于“开始”,终于“结束”, 并经过所有“必须通过”节点(以任何顺序)。
( http://3e.org/local/maize-graph.png / http://3e.org/local/maize-graph.dot.txt 是所讨论的图表 - 它代表了宾夕法尼亚州兰开斯特的一个玉米迷宫)
运行 Djikstra 算法 来查找所有关键节点(起点、终点和必经节点)之间的最短路径,然后深度优先遍历应该会告诉您通过结果子图触及所有节点起点...必经节点...终点的最短路径