10

假设给定一个加权图 G(V,E)。

该图包含N个顶点（编号从 0 到 N-1）和M 个双向边。

每条边(vi,vj)都有正距离d（即两个顶点vivj之间的距离为d）

任何两个顶点之间最多有一条边，也没有自环（即，没有边将顶点连接到自身。）

我们也给定S源顶点和D目标顶点。

令Q为查询数，每个查询包含一条边e(x,y)。

对于每个查询，假设原始图中不存在边 (x,y)，我们必须找到从源 S 到目标 D 的最短路径。 如果从 S 到 D 不存在任何路径，那么我们必须打印 No。

约束很高 0<=(N,Q,M)<=25000

如何有效地解决这个问题？

到目前为止，我所做的是实现了简单的Dijakstra 算法。

对于每个查询 Q，每次我将 (x,y) 分配给 Infinity 并找到 Dijakstra 最短路径。

但是这种方法会很慢，因为整体复杂度为Q（Dijastra Shortes 路径的时间复杂度）*

例子：：

N=6,M=9
S=0 ,D=5

(u,v,cost(u,v))
0 2 4
3 5 8
3 4 1
2 3 1
0 1 1
4 5 1
2 4 5
1 2 1
1 3 3

Total Queries =6

Query edge=(0,1) Answer=7
Query edge=(0,2) Answer=5
Query edge=(1,3) Answer=5
Query edge=(2,3) Answer=6
Query edge=(4,5) Answer=11
Query edge=(3,4) Answer=8
4

3 回答 3

3

首先，计算从源节点到目的地的最短路径树。

其次，遍历所有查询，并在查询指定的边缘处切割最短路径；这定义了一个最小切问题，其中您有源节点与一个分区的边界以及另一个和目标的边界之间的距离；你最多可以很容易地计算这个问题O(|E|)。

因此，当 时，该算法需要O(Q|E| + |V|log|V|)比天真的解决方案 渐近地快|V|log|V| > |E|。

该解决方案重用了 Dijkstra 的计算，但仍单独处理每个查询，因此通过观察边缘诱导的切割形状，利用在连续查询中先前查询中所做的工作，也许还有改进的空间。

于 2012-06-05T10:26:47.567 回答
1

对于每个查询，图形变化很小，因此您可以重用大量计算。

我建议采用以下方法：

  1. 计算从S到所有其他节点的最短路径（Dijkstras 算法已经为您完成了）。这将为您提供最短路径树T。
  2. 对于每个查询，取这棵树，由查询中的边 (x,y) 修剪。这可能是原始树（如果 (x,y) 不在树上的任何位置）或较小的树T'。
    • 如果D在T'中，则可以取原来的最短路径
    • 否则启动 Dijkstra，但使用T'中已有的标签（这些路径已经最小）作为永久标签。

如果您在步骤 2 中运行 Dijkstra，您可以通过以下方式重用树T的修剪部分：每次您想要标记一个永久节点（这是不在T'中的节点之一）时，您可以附加整个子树将此节点（从原始树T）复制到新的最短路径树，并将其所有节点标记为永久。

这样，您可以从第一次最短路径运行中重用尽可能多的信息。

在您的示例中，这意味着：

计算最短路径树：0->1->2->3->4->5（本例非常简单）

现在假设我们得到查询（1,2）。

我们修剪边缘 (1,2)，留下 0->1

从那里我们开始 Dijkstra 获得 2 和 3 作为下一个永久标记节点。我们在新的最短路径树中连接 1 到 2 和 1 到 3，并从 3 附加旧子树： 2<-0->1->3->4->5

因此，我们只需运行 Dijkstras 算法的一个额外步骤就得到了最短路径。

算法的正确性源于树T中的所有路径最多与来自查询的新图中一样长（其中每条最短路径只能更长）。因此，我们可以重用树中仍然可行的每条路径（即没有删除边的地方）。

如果性能很重要，您可以通过许多实现技巧来提高 Dijkstra 的性能。一个很好的切入点可能是DIMACS Shortest Path Implementation Challenge。

于 2012-06-05T11:51:00.663 回答
0

一个简单的优化：首先在完整图上运行 Dijkstra（不删除边）。

然后，对于每个查询 - 检查请求的边缘是否属于该最短路径。如果没有 - 删除这个边缘不会有任何区别。

于 2012-06-05T10:15:23.927 回答