算法

本 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 算法,但为了支持灵活性而牺牲了其部分效率,包括:

  • 任意数量的最短路径(不一定代价相等)
  • 客户端定义的路径可接受性过滤器(通过回调)

本站文档由 北京智网畅联科技有限公司 整理、翻译并提供 · Documentation compiled and provided by Beijing ZNetLink Technology Co., Ltd.

交流群 · QQ Group:OPNET/智网妙算网络仿真交流群(群号 486383494)

原文档 © 2017 Riverbed Technology · 本站为公益翻译,由 AI 辅助完成,请仔细甄别

Original documentation © 2017 Riverbed Technology. Community translation, AI-assisted. Contact: jiazequn@znetlink.com