Geek asks and answers

Shortest Path Algorithm Variation

We are assigned a weighted undirected graph with two sources and two target vertices (for example, s1, s2, d1, d2). To go from source 1 to destination 1 and source 2 to destination 2, the cost is defined as:

  • The cost of using a rib is equal to weight if the rib is used for only one of two paths.
  • the cost of using an edge is 1.5 times the weight if the edge is used both for paths (both s1 → ..-> d1 and s2 → ..-> d2).

Thus, if two paths use the same edge, the total cost increases by "1.5 x weight" instead of "2 x weight". Common edges are recommended.

If the paths use an edge with opposite directions, this does not reduce the cost.

Any help, ideas or suggestions for defining an algorithm that minimizes overall cost?

+3
source share
2 answers

I would suggest first finding the shortest path of all pairs using Floyd Warshall in O (n ^ 3) time, where n is the number of vertices.

After that, you can calculate the transition cost s1-> d1 and s2-> d2 along the shortest paths, which gives you an upper bound on the cost.

The only way to succeed is to use a common path. If so, then s1 and s2 converge at the vertex A, then follow the common path to the vertex B, and then split into d1 and d2.

, , A, B d (x, y), :

d(s1,A)+d(s2,A)+1.5*d(A,B)+d(B,d1)+d(B,d2)

O (n ^ 2), O (n ^ 2) + O (n ^ 3) = O (n ^ 3)

+7

@Peter de Rivaz , O(n^3) . O(n^4), (. ):

n^2, node (a, b) a b . : (a, b) (c, d) iff:

  • a c a == b,
  • b d b == d

. , a = b c = d, , 1,5.

(s1, s2) (d1, d2). , .

:

Floyd , . , , " " , "": , , .

0

More articles:


All Articles