路由表
当后续需要用到从顶点到目的节点的下一跳边时,可使用该 API 生成路由表。
单源路由表(1–>All)
问题
为单一源生成路由表,其中包含从该源节点到每一个其他目的地的第一跳信息。
单源路由表信息不足以找到源与任意目的地之间的完整路径。这些信息只能用于获取一组下一跳边,这些边将用于从源到目的地的路由。每个下一跳边代表通往目的地的完整最低代价路径的第一跳。
最高效的解法是先计算源节点的路由表,然后逐一检索到各目的地的下一跳。
使用指南
prg_djk_single_source_compute()— 计算单一源与所有目的地之间的最短路径。利用这些信息在源节点上构建路由表。prg_djk_next_hops_get()— 检索作为通往目的地最低代价路径第一跳的出边集合。
如果只需要到少数几个目的地的下一跳(而非完整路由表),则对每个 (src,dest) 对使用单对方法、从该对的最短路径向量中获取每条路径的第一跳,可能更为高效。
例如,一项在示例网络上的研究表明,在一个 100 节点的示例网络中,盈亏平衡点出现在从单一源查找 12 个目的地的下一跳时。经验法则:若要从某一源查找超过 10% 目的地的下一跳,就使用 prg_djk_single_source_compute() 方法。
全源路由表(All–>All)
问题
计算所有节点的路由表,并检索从每个源到每个目的地的下一跳信息。
使用指南
prg_djk_all_sources_compute()— 计算图中每个顶点的路由表,并将其作为状态信息存储在图中的每个顶点上。prg_djk_next_hops_get()— 从存储在源顶点上的状态信息中检索源与目的地之间的下一跳集合。