在一个图中找到访问特定节点的最短路径。

Question

99

我有一个大约有100个节点和200条边的无向图。其中一个节点标记为“起点”，一个标记为“终点”，还有大约十几个节点被标记为“必经之路”。

我需要找到通过这个图的最短路径，从“起点”开始，以“终点”结束，并且经过所有“必经之路”的节点（无论顺序如何）。

(该图代表了宾夕法尼亚州兰开斯特的一个玉米迷宫。图片链接：http://3e.org/local/maize-graph.png，文本链接：http://3e.org/local/maize-graph.dot.txt)

- dmd

11个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Stridemann · Answer 1

我试过模拟退火、分支定界、蚁群算法等等，但它们解决中等规模的图形时所需的时间实在是太长了。

因此，我为大型图形设计了快速响应的解决方案（适用于游戏开发中运行时计算）。

该算法已经在这里发布和记录（附有动画）：https://github.com/Stridemann/TravelShortPathFinder

如果您已经有一张图形（在您的情况下是这样），则可以跳过空间划分算法部分。