a variation of shortest path algorithm

Question

We're given a weighted undirected graph with two sources and two destination vertices (say s1, s2, d1, d2). For going from source 1 to destination 1 and source 2 to destination 2 cost is defined as:

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

In summary, if two paths use the same edge, the total cost increases "1.5 x weight" instead of "2 x weight". Using common edges is encouraged.

If paths uses an edge with opposing directions, it doesn't reduce the cost.

Any help, ideas, or suggestions to determine an algorithm which minimizes the total cost?

Answer 1

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

Once you have it you can compute the cost of going s1->d1 and s2->d2 along the shortest paths which gives you an upper bound for the cost.

The only way of doing better is by using a shared path. If so, then s1 and s2 will converge at a vertex A, then go along a shared path to a vertex B, then split to go to d1 and d2.

So the algorithm is to try all pairs of vertices A,B and using your precomputed shortest path between pairs d(x,y) compute the smallest value of:

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

This search is O(n^2), so overall the cost is O(n^2)+O(n^3) = O(n^3)