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

Question

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

我发现了这个： 查找两个顶点之间的所有最短路径 ，但答案对我来说似乎很模糊。

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

Answer 1

这个想法是使w2重要的——但不足以影响他们的结果w1。

让SUM2是w2所有边上的总和：SUM2 = Sum { w2(e) | e in 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与任何最短路径算法一起使用以获得所需的最短路径。