Gra*_*y S 2 language-agnostic algorithm graph-theory breadth-first-search shortest-path
我正在寻找解决最短路径问题的最佳方法:
我有一个带有未加权边缘的有向图.如果存在这样的路径,我需要能够找到任意两个节点之间的最短路径.使这个问题与常规最短路径问题不同的是:如果存在具有最短长度的多个路径,我需要能够选择具有最高"权限"的路径.
每个节点都有一个数字权限,具有最高权限的路径只是具有最高节点权限总和的路径.
总结: 我需要有向图中一对节点之间的最短路径,但如果有多条路径具有相同的最小长度,我需要找到具有最高路径权限的路径.
这样做的最佳方法是什么？有没有办法将其转换为加权图,然后只使用Dijkstra的算法？有没有办法修改广度优先搜索给我一组最短路径,然后我可以迭代查找最高权限路径？
边缘没有加权,所以给eacn边缘一个重量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[通过除法,所以边缘的权限仍将与原始的成比例]
找到的最短路径必须是最短的,因为权威因素不能克服距离因子,因为它是"弱"[归一化到小于1].
并且它是具有最高authority [对于顶点]的那个,因为它是具有最低auth[对于边缘]的那个,因为它是最小的.