算法
本 API 中有三大类算法:Dijkstra、shortest-cycle(最短环)和 k-paths(K 路径)。
本 API 中有两大类算法:Dijkstra 和 k-paths(K 路径)。
Dijkstra
这是标准 Dijkstra 算法的一种变体(算法细节参见参考资料 1、3 和 4)。它能高效地计算从源到某个目的或到所有目的的最短路径。DJK 包的实现支持以下内容:
- 客户端定义的即时边考察(通过一个接受或拒绝路径中边的回调)
- 客户端定义的即时路径考察(通过一个接受或拒绝候选路径的回调)
- 跳数限制,返回不超过
H条边的最短路径 - 检索所有代价相等的最短路径
- 检索最先找到的最短路径
Shortest-Cycle(最短环)
这些用于边不相交和顶点不相交的最短路径对(及其最大化近似)的算法基于参考资料 2 中的算法。回顾一下,cycle(环)是具有共同源和目的的一对路径。
本 API 中的环有四种类型:
- vertex-disjoint(顶点不相交)
- maximally (approximately) vertex-disjoint(最大(近似)顶点不相交)
- edge-disjoint(边不相交)
- maximally (approximately) edge-disjoint(最大(近似)边不相交)
“最大顶点不相交最短对”是在相交顶点数最少的路径对中总代价最小的一对。
“最大边不相交最短对”是在相交边数最少的路径对中总代价最小的一对。
K-Paths(K 路径)
该算法基于 Dijkstra 算法,但为了支持灵活性而牺牲了其部分效率,包括:
- 任意数量的最短路径(不一定代价相等)
- 客户端定义的路径可接受性过滤器(通过回调)