缺少给定边的最短路径
假设我们有一个加权图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
首先，计算从源节点到目的地的最短路径树。
其次，遍历所有查询并在查询指定的边上剪切最短路径; 这定义了一个min-cut问题，在这个问题中，源节点和一个分区的边界之间的距离以及另一个分区的边界和目的地的边界; 你可以很容易地计算这个问题，最多O(|E|) 。
因此，当|V|log|V| > |E|时，该算法需要O(Q|E| + |V|log|V|)渐近地快于初始解|V|log|V| > |E| |V|log|V| > |E| 。
这个解决方案重用了Dijkstra的计算，但仍然单独处理每个查询，所以也许通过观察由边缘引起的切割的形状来利用在先前查询中在连续查询中所做的工作，可能有改进的余地。
对于每个查询，图形只会非常轻微地变化，因此您可以重复使用大量的计算。
我建议采用以下方法：
如果在步骤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 < - > 1-> 3-> 4-> 5的旧子树
所以我们得到了最短路径，只需运行一个额外的Dijkstras算法步骤。
算法的正确性来自树T中的所有路径，最多只要来自查询的新图（其中每条最短路径只能更长）。 因此，我们可以重用仍然可行的树中的每条路径（即没有删除边的地方）。
如果性能很重要，可以通过很多实施技巧来提高Dijkstra的性能。 一个好的切入点可能是DIMACS最短路径实施挑战。
一个简单的优化：首先在完整的图表上运行Dijkstra（没有删除边缘）。
然后，对于每个查询 - 检查请求的边是否属于该最短路径。 如果没有 - 删除这个边缘不会有任何区别。
链接地址: http://www.djcxy.com/p/35293.html上一篇: Shortest path in absence of the given edge
下一篇: Shortest path from single source to single destination in a graph