定义

graph(图)

图是一组顶点及其边关系的集合。

vertex(顶点)

顶点是图中的一条边可以充当端点的节点。

edge(边)

边是连接两个顶点的链路。边可以是无向的或有向的。

path(路径)

路径是从源顶点到目的顶点的一系列边,以边的 PrgT_Vector 表示。在路径中,任何顶点或边都不重复。

route(路由)

route 是 path 的另一种说法。

hop(跳)

hop 是路径中从一个顶点经由一条边到达另一个顶点的有向步骤。路径的跳数(hop length)是路径中边的数量。一跳路径是只包含一条边的 PrgT_Vector。

vertex-disjoint(顶点不相交)

如果两条路径位于相同的源和目的之间,并且除源和目的外不共享任何公共顶点或边,则称这两条路径是 vertex-disjoint(顶点不相交)的。

edge-disjoint(边不相交)

如果两条路径位于相同的源和目的之间,并且不共享任何公共边,则称这两条路径是 edge-disjoint(边不相交)的。

shortest-path(最短路径)

shortest-path 是总长度不长于具有相同源和目的的任何其他路径的路径。注意,一对(源,目的)可能有多条代价相等的最短路径。路径的长度(代价)是路径中各边权重之和。

cycle(环)

在本 API 中,cycle 是共享相同源和目的的一对路径(传统环的两个半环)。cycle 以长度为 2 的 PrgT_Vector 表示,其每个元素都是上述定义的路径,但两条路径之间一般可以具有任意指定的关系(不一定 vertex-disjoint)。

shortest-cycle, shortest-pair(最短环、最短对)

shortest-cycle(或 shortest-pair)是总长度最短、且满足或最佳逼近指定约束(顶点不相交或边不相交)的一对路径(环)。

predecessor list(前驱表)

顶点的前驱表存储从源顶点出发的最短路径树中的边集合。如果从源顶点到某个目的顶点只有一条最短路径,则该表中只有一个条目。可以沿着前驱信息从目的顶点回溯到源顶点,从而构造出完整的路径。在本 API 中,前驱信息用于存储从一个源顶点出发的最短路径树。

routing table(路由表)

顶点的路由表是一种高效的数据结构,用于存储从该顶点到任意目的顶点的下一跳边集合。每个下一跳边都是从该顶点到目的顶点的最短路径中的第一跳。若要利用路由表构造完整的路径,路径中的每个顶点都必须定义了路由表。

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