知识卡片
从目的点父链求源点下一跳
先找到目的顶点,再沿parent反向查找,直到父节点为根;其子节点是从源出发的下一跳。图中gw1到gw2经gw3、gw6,下一跳为gw3;从gw2出发无法到gw1,应没有该目的地条目。不同源点的最短路径树和下一跳可以不同。
route每次沿父链用match线性扫描paths,链长最多n时开销O(n²)。找不到目的或父节点返回−1,输出next未预先清空;若目的就是根,源码返回根本身,调用方应另定义本地目的的处理。若错误父链成环,循环没有检测,可能不终止。
next借用图顶点,路径列表和原图相关对象的寿命都要保持。图例只是简化模型,不表示互联网所有路由器都保存完整互联网拓扑或始终立即收敛。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
下一个网关。路由器的目的就是将数据包往最接近于目的地的地方发送。 为了将数据包往更接近其目的地的地方发送,每个路由器都要维护互联网的结构信息或拓扑信息。这些信息存储在路由表中。路由表为每个路由器知道如何到达的网关存储一个条目。每个条目指定把数据包发送到下一个网关的地址。 由于路由器会周期性地随着互联
参考来源
- 位置:《算法精解:C语言描述》第16章《最短路径的例子:路由表》(spine1415;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1381.html;u300-ch16-011)。
- 结论依据:300全文、03089两源路由表及03090–03091完整route代码实际阅读。
- 原始内容:下一个网关。路由器的目的就是将数据包往最接近于目的地的地方发送。 为了将数据包往更接近其目的地的地方发送,每个路由器都要维护互联网的结构信息或拓扑信息。这些信息存储在路由表中。路由表为每个路由器知道如何到达的网关存储一个条目。每个条目指定把数据包发送到下一个网关的地址。 由于路由器会周期性地随着互联