最短路径算法的一种变体 [英] a variation of shortest path algorithm
问题描述
我们给了一个加权无向图，它带有两个源和两个目标顶点(例如s1，s2，d1，d2).从来源1到目的地1，从来源2到目的地2的费用定义为:
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:
- 如果仅使用两条路径之一，则使用边缘的成本等于权重. 如果在两条路径(s1-> ..-> d1和s2-> ..-> d2)中都使用边缘，则使用边缘的成本等于重量的1.5倍.
- 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).
总而言之，如果两条路径使用同一条边，则总成本将增加"1.5 x权重"，而不是"2 x权重".鼓励使用公共边缘.
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.
一旦有了它，您就可以计算出沿着最短路径s1-> d1和s2-> d2的成本，这为您提供了成本上限.
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.
做得更好的唯一方法是使用共享路径.如果是这样，则s1和s2将在顶点A处收敛，然后沿着共享路径到达顶点B，然后分裂为d1和d2.
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.
因此，算法是尝试所有顶点A，B对，并使用预先计算的对之间的最短路径d(x，y)计算最小值:
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)
此搜索为O(n ^ 2)，因此总成本为O(n ^ 2)+ O(n ^ 3)= O(n ^ 3)
This search is O(n^2), so overall the cost is O(n^2)+O(n^3) = O(n^3)
这篇关于最短路径算法的一种变体的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
