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

Question

Given a weighted directed graph G = (V, E) , a source vertex s , a destination vertex t and a subset v’, how to finds the shortest non-loop path from s to vertex t in the graph? The vertexs in the subset must be included in the path.

Answer 1

这是旅行商问题 (TSP)的变体。

您可以通过在图中运行 all-to-all 最短路径（Floyd Warshall 算法）将您的问题转换为 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)

现在，找到通过 中所有节点 (TSP)G'的最小路径也是满足标准的最小路径（在将两对之间的每条路径向后扩展之后）。

不幸的是，TSP 是NP-Complete问题（没有已知的多项式时间算法来解决它，并且大多数人认为甚至不存在），除非您的“必须通过节点”的集合V'相对较小（并且您负担得起算法的指数时间运行时间），您将需要选择一个“足够好”的算法，这可能不是最佳的。

---

关于“无循环”的旁注 - 请注意它可能不可行，例如：

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

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