如何在特殊情况下找到最短路径成本？

Question

给定一个加权有向图 G = (V, E) 、源顶点 s 、目标顶点 t 和子集 v'，如何在图中找到从 s 到顶点 t 的最短非循环路径？子集中的顶点必须包含在路径中。

Answer 1

这是 Traveling Salesman Problem (TSP) 的变体。

您可以通过运行图中所有到所有的最短路径 (Floyd Warshall Algorithm) 将您的问题转换为 TSP 的精确实例，然后创建一个新图：

G'={V' U {s,t}, E'}
V' - the "must go through" subset
E' = { (s,v), (v,t), (u,v) | u,v in V'}  (In words: all edges between two nodes in the new graphs)

现在，求出经过G'中所有节点（TSP）的最小路径，也是满足条件的最小路径（将两对之间的每条路径向后展开）

不幸的是，TSP 是 NP-Complete 问题（没有已知的多项式时间算法来解决它，大多数人认为甚至不存在），除非你的 "must go through nodes" V' 相对较小（并且您可以负担算法的指数时间运行时间），您将需要选择 "good enough" 算法，这可能不是最优的。

关于 "no loops" 的旁注 - 请注意它可能不可行，例如：

      ---------
     |         |
     v         |
s -> a -> b -> c
     |
     |
     t

在这个例子中，唯一满足条件的路径是s->a->b->c->t

如何在特殊情况下找到最短路径成本？

How to find the shortest path cost with under special conditions?

graph

path

shortest