Shortest path in absence of the given edge

 

Suppose we are given a weighted graph G(V,E).

The graph contains N vertices (Numbered from 0 to N-1) and M Bidirectional edges .

Each edge(vi,vj) has postive distance d (ie the distance between the two vertex vivj is d)

There is atmost one edge between any two vertex and also there is no self loop (ie.no edge connect a vertex to itself.)

Also we are given S the source vertex and D the destination vertex.

let Q be the number of queries,each queries contains one edge e(x,y) .

For each query,We have to find the shortest path from the source S to Destination D, assuming that edge (x,y) is absent in original graph. If no any path exists from S to D ,then we have to print No.

Constraints are high 0<=(N,Q,M)<=25000

How to solve this problem efficiently?

Till now what i did is implemented the simple Dijakstra algorithm.

For each Query Q ,everytime i am assigning (x,y) to Infinity and finding Dijakstra shortest path.

But this approach will be very slow as overall complexity will be Q(time complexity of Dijastra Shortes path)*

Example:: 

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

First, compute the shortest path tree from source node to destination.

Second, loop over all the queries and cut the shortest path at the edge specified by the query; this defines a min-cut problem, where you have the distance between the source node and the frontier of one partition and the frontier of the another and the destination; you can compute this problem very easily, at most O(|E|) .

Thus, this algorithm requires O(Q|E| + |V|log|V|) , asymptotically faster than the naïve solution when |V|log|V| > |E| |V|log|V| > |E| .

This solution reuses Dijkstra's computation, but still processes each query individually, so perhaps there are room to improvements by exploiting the work did in a previous query in successive queries by observing the shape of the cut induced by the edge.

For each query the graph changes only very slightly, so you can reuse a lot of your computation.

I suggest the following approach:

  • Compute the shortest path from S to all other nodes (Dijkstras Algorithm does that for you already). This will give you a shortest path tree T .
  • For each query, take this tree, pruned by the edge (x,y) from the query. This might be the original tree (if (x,y) was no where on the tree) or a smaller tree T' .
  • If D is in the T' , you can take the original shortest path
  • Otherwise start Dijkstra, but use the labels you already have from the T' (these paths are already smallest) as permanent labels.

    • If you run the Dijkstra in step 2 you can reuse the pruned of part of tree T in the following way: Every time you want to mark a node permanent (which is one of the nodes not in T' ) you may attach the entire subtree of this node (from the original tree T ) to your new shortest path tree and label all its nodes permanent.

    This way you reuse as much information as possible from the first shortest path run.

    In your example this would mean:

    Compute shortest path tree: 0->1->2->3->4->5 (in this case a very simple)

    Now assume we get query (1,2).

    We prune edge (1,2) leaving us with 0->1

    From there we start Dijkstra getting 2 and 3 as next permanent marked nodes. We connect 1 to 2 and 1 to 3 in the new shortest path tree and attach the old subtree from 3: 2<-0->1->3->4->5

    So we got the shortest path with just running one additional step of Dijkstras Algorithm.

    The correctness of the algorithm follows from all paths in tree T being at most as long as in the new Graph from the Query (where every shortest path can only be longer). Therefore we can reuse every path from the tree that is still feasible (ie where no edge was removed).

    If performance matters a lot, you can improve on the Dijkstra performance through a lot of implementation tricks. A good entry point for this might be the DIMACS Shortest Path Implementation Challenge.

    One simple optimization: first run Dijkstra on complete graph (with no edges removed).

    Then, for each query - check if the requested edge belongs to that shortest path. If not - removing this edge won't make any difference.

    链接地址: http://www.djcxy.com/p/35294.html

    上一篇: 访问k个顶点的无向图中的最短路径

    下一篇: 缺少给定边的最短路径