如何找到有向图中，必须通过特定节点的最短路径？

我有小于600个节点的有向图，以及每个节点的边数是小于8 现在我需要找到在该曲线图中，其必须通过一些给定节点（< 50）的路径。传递给定节点的顺序是免费的。我知道这是一个NPC问题，但我不知道如何解决它。的近似解也是可接受的。谢谢！如何找到有向图中，必须通过特定节点的最短路径？

2016-03-09 skillness

[奇怪的话题（ https://xkcd.com/69/） – Shark

贵路径开始，并在特定节点结束？你是否需要为不变的图找到很多具有不同开始/结束节点的路径？ – MrSmith42

不会有一个bfs解决方案为你做的伎俩？从您的路径中获取第一个节点。检查它的邻居并重复，直到遍历节点集合不包含路径中的所有节点[你提到它必须通过一些节点，所以我假设路径也可以包含其他节点。] –

计算所有对特定的节点之间的最短途径。然后创建一个只包含那些节点的新图，其中最短路径的长度为距离。现在，问题“减少”到旅行推销员。

（TSM具有快速3/2-近似值utilitizes最小生成树和匹配，如果这是不够好 - ！50可能性太多了在任何情况下）

2016-03-09 08:54:12 Aziuth

回答