a variation of shortest path algorithm
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:
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?
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 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:
a to c or a == b , and 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.
链接地址: http://www.djcxy.com/p/6008.html上一篇: 具体图和一些关于最短路径的声明？
下一篇: 最短路径算法的变体