我正在寻找解决最短路径问题变体的最佳方法:
我有一个带未加权边的有向图。如果存在这样的路径，我需要能够找到任意两个节点之间的最短路径。这个问题与常规最短路径问题的不同之处在于:如果存在多条长度最短的路径，我需要能够选择具有最高“权限”的路径。
每个节点都有一个数字权限，权限最高的路径就是节点权限总和最高的路径。
总结: 我需要有向图中一对节点之间的最短路径，但如果有多条路径具有相同的最小长度，我需要找到具有最高路径权限的路径。
执行此操作的最佳方法是什么？有什么方法可以将其转换为加权图然后使用 Dijkstra's algorithm ？有什么方法可以修改 breadth-first search给我一组最短路径，然后我可以遍历这些路径以找到最高权限路径？
最佳答案
边没有加权，所以给每条边赋予1+auth(v,u)的权重. [身份验证在以下行中解释]
对于每个 (v,u) 集 auth(v,u) = max{authority} - authority(v) (*) [这是真的，因为如果你使用离开 v 的边缘，您绝对访问过它]。
(*) max{authority}是图中的最高权限。
规范化您的“授权等级”，Sigma(auth(v,u),for each (v,u) in E) < 1 [通过除法，所以edges的权限还是会和原来成正比]
现在，运行 dijkstra在具有新修改权重的图表上。
找到的最短路径一定是最短，因为权威因素无法战胜距离因素，因为它要'弱'[归一化为小于1]。
而且是最高的authority [对于顶点]，因为它是 auth 最低的那个[对于边缘]，因为它是最小的。
关于algorithm - 在多个最短路径之间具有选择标准的有向未加权图中的最短路径？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/8610788/