小编sta*_*ler的帖子

我们给出了一个带有两个源和两个目标顶点(比如s1,s2,d1,d2)的加权无向图.从源1到目的地1和源2到目的地2的成本定义为:

• 如果边缘仅使用两条路径中的一条,则使用边缘的成本等于权重.
• 如果边缘被用于两个路径(s1 - > ..-> d1和s2 - > ..-> d2),则使用边缘的成本等于权重的1.5倍.

总之,如果两条路径使用相同的边缘,则总成本增加"1.5 x重量"而不是"2 x重量".鼓励使用共同边缘.

如果路径使用具有相反方向的边缘,则不会降低成本.

有任何帮助,想法或建议来确定最小化总成本的算法吗？