最短路径上的变化（复数？）

Question

我有以下问题。给定一个有向图G =（V，E），所有边{i，j}之间的边成本cij。我们有多个来源，比如s1，...，sk和一个目标，比如t。问题是找到从s1，... sk到t的最低组合成本，其中所有不同路径的访问顶点总数为M.（源和目标不计为已访问顶点，并且0 < = M < = | V | -k + 1，所以如果M = 0所有路径直接从源到目标）。

1. 问题是由刚刚扭转所有的边缘，使源目标和目标源类似的多重目标（T1，...，TK）和一个源。我认为这可能是有用的，因为例如Dijkstra计算图中从一个源到所有其他顶点的最短路径。

2. 只有一个目标和一个源，可以找到最大的最短路径。用Bellman Ford算法计算访问顶点的数量M.这是通过迭代地增加访问顶点的数量来完成的。

3. 寻找从一个源到一个目标的最短路径而需要访问顶点v1，...，vk的问题对于小k可以如下求解：i）计算所有节点之间的最短路径顶点。 ii）检查哪个k！排列是最短的。 我认为这可能是有用的时，我将调整后的问题1）转变为从一个源到一个“超级”的问题，强制访问“旧”目标t1 = v1，...，tk = vk。

不幸的是，组合1,2和3不提供解决方案，但它可能有所帮助。有谁知道解决方案？这可以有效解决吗？

Answer 1

为什么不为每个s做​​一个单独的Dijkstra，然后总结成本？

喜欢的东西：

float totalCost; 
for (int i=0; i<k; i++) 
    totalCost += Dijkstra(myGraph,s[i],t); 

我希望我理解正确的问题。