3

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?

Ali
  • 56,466
  • 29
  • 168
  • 265
stationary traveller
  • 33
  • 3

2 Answers2

7

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)

Peter de Rivaz
  • 33,126
  • 4
  • 46
  • 75
  • Should be ...+d(B,d1)+d(B,d2), not s1/s2 – abraabra Feb 25 '14 at 22:13
  • Why can't it happen that the shortest partially shared path alternates between shared subpaths and unshared subpaths? Because if that happens, then this won't find that kind of path if I understood it correctly. – G. Bach Feb 26 '14 at 03:09
  • 2
    @G.Bach Suppose the shortest path is shared A->B, then not shared B->C, then shared C->D. Consider the two unshared routes B->C. Suppose person1 costs x, person 2 costs y. It will always be better to make the slower person go along the same route as the faster one. The cost taking the shared route will be 1.5(min(x,y)) which is never worse than x+y – Peter de Rivaz Feb 26 '14 at 09:02
0

@Peter de Rivaz provides a solution that runs in O(n^3) based on Floyd's algorithm. The following alternative is based on Dijkstra's algorithm and runs in O(n^4), but may be applicable in a more general problem setting (see addendum):

Generate a new graph with n^2 nodes, where each node (a, b) in the graph corresponds to a combination of two nodes a and b in the original graph. The nodes of this new graph are connected as follows: there is an edge between (a, b) and (c, d) iff:

  • there is an edge from a to c or a == b, and
  • there is an edge from b to d or b == d

in the original graph. The cost of this new edge corresponds to the sum of the two edges in the original graph, unless a = b and c = d, in which case the cost is the sum of the original edge multiplied by 1.5.

This new graph also includes two nodes (s1, s2) and (d1, d2). Simply determine the shortest path between these two nodes, and the individual paths in the original graph are easily deduced.

Addendum:

The main advantage to the Floyd-based approach is that you get more flexibility with regard to modifications of the problem statement. For example, it is possible to solve a variation of the problem where the "sharing discount" is only awarded if the two travellers share the edge in the same "step": all you need to do is adjust the weights accordingly.

blubb
  • 9,510
  • 3
  • 40
  • 82