缺少给定边的最短路径

Question

假设给出加权图G（V，E）。

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

每个边缘（六，VJ）具有阳性距离d（即，在两个顶点vivj之间的距离是d）

有任意两个顶点之间atmost一个边缘，并且还存在没有自我循环（ie.no边缘顶点连接到 本身。）

此外，我们给出小号源顶点和d目标顶点。

let Q是查询的数量，每个查询包含一个边沿e（x，y）。假设边缘（x，y）在原始图中不存在，我们必须找到从源S到目的地D的最短路径。 如果没有从S到d存在任何路径，则我们有打印号

约束是高0 < =（N，Q，M）< = 25000

如何解决这个问题有效？

直到现在我所做的是实现了简单的Dijakstra算法。

对于每个查询Q，每次我很分配（X，Y），以无限 和发现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 

Answer 1

首先，计算从源节点到目的地的最短路径树。其次，遍历所有查询并在查询指定的边上剪切最短路径;这定义了一个min-cut问题，在这个问题中，源节点和一个分区的边界之间的距离以及另一个分区的边界和目的地的边界;你可以很容易地计算这个问题，最多O(|E|)。

因此，该算法需要O(Q|E| + |V|log|V|)，当|V|log|V| > |E|时渐近地快于初始解。

该解决方案重用了Dijkstra的计算，但仍然单独处理每个查询，因此可能还有空间通过观察由边缘引起的切割的形状来利用在先前查询中在连续查询中所做的工作。

Answer 2

一个简单的优化：第一上运行的Dijkstra完整的图形（没有删除边缘）。

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

Answer 3

对于每个查询，图只会非常轻微地改变，因此您可以重复使用很多计算。

我建议以下方法：

1. 计算从小号到所有其他节点的最短路径（Dijkstras算法并为你的话）。这会给你一个最短路径树T。
2. 对于每个查询，取这棵树，用查询中的边（x，y）修剪。这可能是原始树（如果（x，y）不在树上的任何位置）或更小的树T'。
   • 如果d在T“，你可以把原来的最短路径
   • 否则启动Dijkstra算法，而是使用你已经从T的标签”（这些路径已经是最小的）作为永久性标签。

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

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

---

在您的例子，这将意味着：

计算最短路径树： 0-> 1-> 2-> 3-> 4-> 5 （在这种情况下很简单的）

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

我们修剪边缘（1,2）留给我们 0-> 1

从那里，我们开始的Dijkstra得到2个3下一个永久标记节点。 我们连接1至2和1至3个新的最短路径树，并附上3老树： -0-> 1-> 3-> 4-> 5

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

---

算法的正确性从所有路径遵循在树Ť至多为只要在从查询（其中每个最短路径只能更长）的新图形。因此，我们可以重用仍然可行的树中的每条路径（即没有删除边的地方）。

如果性能很重要，可以通过大量的实施技巧来提高Dijkstra的性能。一个好的入口点可能是DIMACS Shortest Path Implementation Challenge。