没有给定边缘的最短路径

Question

假设给出了加权图G(V,E).

该图包含N个顶点(从0到N-1编号)和M个双向边.

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

有atmost任意两个顶点之间的一个边缘,也有没有自我循环(ie.no边缘的顶点连接到其自身.)

我们也给S是源顶点,D给目标顶点.

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

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

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

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

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

对于每个Query 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

Answer 1

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

\n\n

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

\n\n

因此，O(Q|E| + |V|log|V|)当 时，该算法需要 ，比 na\xc3\xafve 解渐近更快|V|log|V| > |E|。

\n\n

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

\n