在一个有向无权图中，如何在多个最短路径之间选择满足特定条件的最短路径？

Question

我正在寻找解决最短路径问题中的这种变化的最佳方法：

我有一个有向图，具有未加权的边。如果存在这样一条路径，我需要能够找到任意两个节点之间的最短路径。使这个问题与常规的最短路径问题不同的是：如果存在多条具有最短长度的路径，则我需要能够选择具有最高“权威性”的路径。

每个节点都有一个数字权威性，具有最高权威性的路径仅是节点权威性总和最高的路径。

总之： 我需要在有向图中找到一对节点之间的最短路径，但是如果存在多条相同的最小长度路径，则需要找到具有最高路径权威性的路径。

最好的方法是什么？是否有一种方法可以将其转换为加权图，然后只使用Dijkstra算法？是否有一种修改breadth-first search以给出最短路径集合的方法，然后我可以迭代查找最高权威路径？

- Grady S

---

不是的。我应该在问题中更清楚地表达吗？ - Grady S

Answer 1

边没有权重，因此为每条边赋予权重1+auth(v,u)。[在下一行中解释了auth]

对于每个(v,u)设置auth(v,u) = max{authority} - authority(v) (*) [这是正确的，因为如果您使用离开v的边，您肯定会访问它]。

(*)max{authority}是图中最高的权限。

规范化您的“auth rank”，所以Sigma(auth(v,u),for each (v,u) in E) < 1 [通过除法，因此边的权威仍然与原始比例成比例]

现在，在具有新修改的权重的图上运行Dijkstra算法。

找到的最短路径必须是最短的，因为权威因素无法克服距离因素，因为它太“弱”[规范化为小于1]。它是具有最高authority [对于顶点]的路径，因为它是最小的，因此具有最低的auth [对于边]。

- amit

---

我觉得这正是我在寻找的。如果你不介意我提几个澄清问题：在 auth(v,u) 中，v 是边的起点，u 是终点吗？我感觉你可能是在使用标准图表示法，但遗憾的是，我并不完全熟悉它。在 Sigma(auth(v,u),for each (v,u) in E) 中，E 是边集合吗？我明白规范化的目标，但是我不明白你建议我应该如何做（如果你确实提出了一种方法的话）。 - Grady S

(1) 是的，v是源，u是目标。 (2) 是的，E是边集。 (3) 一种归一化的方法是通过将所有边的auth除以max{authority} * (|E| + 1)来实现，这样可以确保所有边的auth之和不会等于或大于1。 - amit

还有一个问题，如果你不介意的话：计算权威性是一项计算密集型的任务，但我知道理论上的最大权威性，它只是节点的数量。我能用这个值作为max{authority}吗？或者必须使用实际的最大权威性？ - Grady S

@类型：（1）它不会太复杂，可以通过设置边集的单一路径来完成，并且最终不会有瓶颈。（2）然而，是的 - 给出理论上的最大{权威}应该足够了。 - amit

好的，谢谢。顺便说一下，我是指根据我定义的方式计算节点的权威性是很昂贵的，它不是一个静态的数字。 - Grady S

Answer 2

迪杰斯特拉算法并不强制使用标量来表示路径成本。

一个简单的修改是使用一对值而不是单个值，例如(距离，权威)来表示路径的成本。排序顺序为<距离，然后是>权威，即较低的距离具有更高的优先级，然后是较高的权威。

- MSN