我正在寻找解决最短路径问题的最佳方法:
我有一个无权边的有向图。我需要找到任意两个节点之间的最短路径，如果这样的路径存在的话。这个问题与常规最短路径问题的不同之处在于:如果存在多条最短长度的路径，我需要能够选择具有最高"权限"的路径。
每个节点都有一个数字权限，具有最高权限的路径就是节点权限总和最高的路径。
在简介:我需要有向图中一对节点之间的最短路径，但如果有多条路径具有相同的最小长度，我需要找到具有最高路径权限的路径。
做这件事的最好方法是什么?有没有办法把它转换成一个加权图然后用Dijkstra算法?有没有办法修改宽度优先搜索，让我得到一组最短路径，然后我可以遍历这些路径，找到最高权限的路径?
边是未加权的，所以给每条边一个1+auth(v,u)的权值。[auth如下行解释]
对于每个(v,u)集合auth(v,u) = max{authority} - authority(v)(*)[这是正确的，因为如果你使用从v出发的边，你肯定访问了它]。
(*) max{authority}为图中最高权威值。
规范化你的"权威等级"，所以，Sigma(auth(v,u),for each (v,u) in E) < 1[通过划分，所以边缘的权威仍然与原来的成比例]
现在，用修改后的新权重在图上运行dijkstra。
找到的最短路径必须是最短的，因为权威因子不能克服距离因子，因为它是"弱"的[归一化到小于1]。
并且它是具有最高authority [对于顶点]的那个，因为它是具有最低auth[对于边]的那个，因为它是最小的。
吉布克斯特拉的算法没有强制您使用标量来表示路径成本。
一个简单的修改是使用一对值而不是单个值，例如(distance, authority)来表示路径的代价。顺序是< distance，然后是> authority，即低distance优先级高，高authority优先级高。