algorithm - 最短路径，2 个权重函数

Question

问题是这样的:给定一个有向图G = (V,E)，两个顶点s,t，两个权重函数w1,w2。G 中没有负加权循环(w1 和 w2)。我需要描述一种算法，它在给定的从 s 到 t 的最短路径s 中，通过 w2 找到从 s 到 t 的最短路径。

我发现了这个: FInding All Shortest Paths Between Two Vertices但答案对我来说似乎很夸张。

我不知道如何解决这个问题(即使是蹩脚的)。任何帮助将不胜感激。

Answer 1

这个想法是让 w2 变得重要 - 但不足以影响 w1 的结果。

设 SUM2 是所有边上 w2 的总和: SUM2 = Sum { w2(e) | e 在 E } 中，min{w1} = min { w1(e) | e in E (根据w1的最小值)

在此基础上，创建新的权重函数:

w(e) = w1(e) + w2(e)/min{w1}*(SUM2+1)

现在，给定所有根据 w1 的最短路径 - 很明显为什么根据 w2 的最短路径将在其中受到青睐。

另一方面，w2 的“强度”不足以克服 w1 的重要性并占据主导地位，因为请注意，根据 w2 现在小于 w1

中的单个节点

将上面的 w 与任何最短路径算法结合使用以获得所需的最短路径。