Geek asks and answers

Algorithm for the Shortest Weighted Path - Frequently Changing Edges

I am trying to solve a graph problem. The schedule is weighted and non-oriented.
Count Size:

no. of vertices upto  200,000 
no. of edges upto  200,000

I have to find the shortest path between the given two nodes (S and D) in the graph. I use Dijkstra algorithmto find this.
Now the problem in the schedule is often changing. I have to find the shortest path between S and D if a specific edge is removed from the graph. I am again calculating a new path using the Dijkstra algorithm, treating the graph as a new graph after removing the edge. However, this approach is too slow, as there may be 200,000 edges, and I will calculate the shortest path 200,000 times for each edge removal.
I thought about using any memoization technique, but I can’t understand how the shortest path can even change if a particular edge is removed from the graph.
// details The

source and destination are captured throughout the problem.
For each edge removal there will be up to 200,000 requests. at that time only one edge is removed from the initial graph for each test case

+5
source share
4 answers

Since no edge has been added, the shortest path after removal will always be greater than (or equal to) the original. If the deleted edge is not part of the original shortest path, the result will not change. If this is part of the original shortest path, then re-executing the algorithm is the worst solution.

If you are not looking for the exact answer, you can try approximate local methods to fill the missing edge.

You can increase the Dijkstra algorithm to store information that will allow you to return to a certain state during the initial search.

, , , , , . .

, , , , , .

+4

:

Dijkstra, Source to Destination, , ( , , ), ( ). , node, node, node .

, ,

, ( ), . . , node, ( ), , .

, :

  • , , , node ,
  • , , .

, node .

, :

        I
       /
  B---E
 /   /   H
A   D   /|
 \ / \ / |
  C---F--G

A H, , 1 ( )

A:

        I
       /
  B---E
 /   /   H
0   D   /|
 \ / \ / |
  C---F--G

H, 0:

        I
       /
  B---E
 /   /   (0)
0   D   / |
 \ / \ /  |
  C---F---G

:

        I
       /
  1---E
 /   /   (0)
0   D   / |
 \ / \ /  |
  1---F---G

, H:

        I
       /
  1---E
 /   /     (0)
0   D     /  |
 \ / \   /   |
  1---(-1)--(-1)

B, C, F G ( ):

        I
       /
  1---2
 /   /     (0)
0   D     /  |
 \ / \   /   |
  1---(-1)--(-1)

C

        I
       /
  1---2
 /   /        (0)
0   2        /  |
 \ / \      /   |
  1---2 & (-1)--(-1)

node, , , A H, node, , , A H A->C->F->H ABS(2)+ABS(-1) = 3

, C- > F                     /     1 --- 2    // (0)   0 2/|    \/\/|     1 2 (-1) - (- 1)

C F ( 1), :

        I
       /
  1---E
 /   /     (0)
0   D     /  |
 \ / \   /   |
  1   (-1)--(-1)

-, B:                     /     1 --- 2    // (0)   0 D/|    \/\/|     1 (-1) - (- 1)

C

        I
       /
  1---2
 /   /     (0)
0   2     /  |
 \ / \   /   |
  1   (-1)--(-1)

F:

        I
       /
  1---2
 /   /         (0)
0   2&(-2)    /  |
 \ /    \    /   |
  1      (-1)---(-1)

, , A H : A- > C- > D- > F- > H ABS(2)+ABS(-2) = 4

, , , , " ".

, node , , , .

, , A->C, C (as )

Dijkstra :

        I
       /
  1---E
 /   /   H
0   D   /|
 \ / \ / |
  1   F--G

B:

        I
       /
  1---2
 /   /   H
0   D   /|
 \ / \ / |
  1   F--G


        I
       /
  1---2
 /   /   H
0   2   /|
 \ / \ / |
  1   F--G

D:

        I
       /
  1---2
 /   /   H
0   2   /|
 \ / \ / |
  1   3--G

:

        3
       /
  1---2
 /   /   H
0   2   /|
 \ / \ / |
  1   3--G

F:

        3
       /
  1---2
 /   /   4
0   2   /|
 \ / \ / |
  1   3--4

, A->C->D->F->H, 4. , 5 , 3, .

, , , , . , 50 H, A H, , , , , , H A, 50 , A.

, ~ 200 000 200 000 , , , , 9 11 . , node, , , .

+4

:

  • Dijkstra Source to Destination.
  • , , . , . , .

:

  • Dijkstra, , .
  • - , , .
0

, . , , , - sp A B (sp (A, B)) node C , sp (A, B ) = sp (A, C) + sp (C, B) ( C).

( ) , . ( ) - , .

0

More articles:


All Articles