0

我有以下问题。给定一个有向图 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. 只需一个目标和一个源，就可以找到最大的最短路径。使用贝尔曼福特算法访问的顶点 M 的数量。这是通过迭代地增加访问顶点的数量来完成的。

  3. 当必须访问顶点 v1,...,vk 时，找到从一个源到一个目标的最短路径的问题，对于较小的 k，可以解决如下： i) 计算所有顶点之间的最短路径。ii) 检查k中的哪一个！排列是最短的。我认为这在将我在 1) 处调整的问题转换为从一个源到一个“超级目标”的问题时很有用，强制访问“旧”目标 t1=v1,...,tk=vk。

不幸的是，结合 1、2 和 3 并不能提供解决方案，但它可能会有所帮助。有谁知道解决方案？能否有效解决？

4

1 回答 1

1

为什么不为每个 s 做一个单独的 Dijkstra，然后将成本相加？

就像是：

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

我希望我正确理解了这个问题。

于 2011-12-05T06:39:18.473 回答