我建议首先使用

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)