Algorithms

There are three main groups of algorithms in this API: Dijkstra, shortest-cycle, and k-paths.

There are two main groups of algorithms in this API: Dijkstra and k-paths.

Dijkstra

This is a variation on the standard Dijkstra’s algorithm (see references 1, 3, and 4 for algorithmic details). It efficiently calculates the shortest path from a source to a destination or to all destinations. The DJK package’s implementation includes support for the following:

  • client-defined just-in-time edge-consideration (via a callback that accepts or rejects edges for a path)
  • client-defined just-in-time path-consideration (via a callback that accepts or rejects a candidate path)
  • hop-limits, returning shortest paths that do not exceed H edges
  • retrieval of all equal-cost shortest-paths
  • retrieval of the first-found shortest path

Shortest-Cycle

These algorithms for edge-disjoint and vertex-disjoint pairs of shortest-paths (and maximal approximations thereto) are based on algorithms found in reference 2. Recall that a cycle is a pair of paths with a common source and destination.

The four types of cycles in this API are:

  • vertex-disjoint
  • maximally (approximately) vertex-disjoint
  • edge-disjoint
  • maximally (approximately) edge-disjoint

“Maximally vertex-disjoint shortest pair” is a pair of minimal total cost among pairs that have the fewest intersecting vertices.

“Maximally edge-disjoint shortest pair” is a pair of minimal total cost among pairs that have the fewest intersecting edges.

K-Paths

This algorithm is based on Dijkstra’s algorithm, but sacrifices some of its efficiency in order to support flexibility, including:

  • Arbitrary number of shortest-paths (not necessarily equal-cost)
  • Client-defined path-acceptability filter (via callbacks)

本站文档由 北京智网畅联科技有限公司 整理、翻译并提供 · 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