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