最短路径上的变化（复杂？）
我有以下问题。 给定一个有向图G =（V，E），所有边{i，j}之间的边成本cij。 我们有多个来源，比如s1，...，sk和一个目标，比如t。 问题是找到从s1，... sk到t的最低组合成本，其中，所有不同路径的访问顶点总数为M.（源和目标不计为访问顶点，0 <= M <= | V | -k + 1，所以如果M = 0，所有路径直接从源到目标。）
我想出了以下内容，但尚未找到解决方案。
这个问题类似于多个目标（t1，...，tk）和一个来源，方法是只颠倒所有边并使源目标和目标源。 我认为这可能很有用，因为例如Dijkstra计算图中从一个源到所有其他顶点的最短路径。
只需一个目标和一个源就可以找到最大的最短路径。 用Bellman Ford算法计算访问顶点的数量M. 这是通过迭代地增加访问顶点的数量来完成的。
寻找从一个源到一个目标的最短路径，而顶点v1，...，vk必须被访问的问题对于小的k可以如下求解：i）计算所有顶点之间的最短路径。 ii）检查哪个k！ 排列是最短的。 我认为这在将我调整后的问题1）转换为从一个源到一个“supertarget”的问题时有用，对“旧”目标t1 = v1，...，tk = vk进行强制访问。
不幸的是，组合1,2和3并不能提供解决方案，但它可能有所帮助。 有谁知道解决方案？ 这可以有效解决吗？
为什么不为每个s做一个单独的Dijkstra，然后总结成本？
就像是：
float totalCost;
for (int i=0; i<k; i++)
totalCost += Dijkstra(myGraph,s[i],t);
我希望我能正确理解这个问题。
链接地址: http://www.djcxy.com/p/35225.html