从多个顶点的最大距离内提取子图的高效算法

Question

我有一个算法问题，其中有一个简单的解决方案，但它看起来很浪费。我想知道是否有更有效的方法来做同样的事情。

这里的问题：

• 输入：一个大的图形G具有非负边缘权重（解释为长度），顶点v的列表，和距离d相同的长度v的列表。
• 输出：子图的GS由所有那些在从v[i]一些i至多d[i]的距离的顶点的。

显而易见的解决方案是使用Dijkstra算法从每个v[i]开始，修改，以便它击中的d[i]的距离，然后取每个搜索遍历子图的工会后捞出。但是，在我的使用案例中，经常会发生来自v[i]的搜索树重叠的情况。这意味着Dijkstra方法会在我进行联合之前多次浪费地遍历重叠中的顶点。

在有只有一个v顶点的情况下，Dijkstra算法的方式在运行O(|S|log|S|)，以|S|是顶点的数目（图表中的数据是稀疏的，所以我忽略边缘项）。当v有多个顶点时，是否可以达到相同的渐近运行时间？

我的第一个想法是将每个v[i]中的搜索合并到同一个优先级队列中，但上面提到的“保释”条件使这种方法变得复杂。有时顶点会在距离一个v[i]较短的距离内到达，但如果第二个顶点有更大的d[j]分配给它，您仍然希望从另一个v[j]搜索它。

谢谢！

Answer 1

您可以用单个Dijkstra运行的复杂性来解决这个问题。

设D是d中距离的最大值。

定义一个新的起始顶点，并给它边缘每个顶点在诉

开始和v之间的边缘的长度[I]应设置为d-d [i]中。

然后在这个新图中，S由开始顶点的长度D内的所有顶点给出，所以将Dijkstra应用于开始顶点。