某网络中的路由器运行OSPF路由协议,题42表是路由器R1维护的主要链路状态信息(LSI),题42图是根据题42表及R1的接口名构造出来的网络拓扑。
题42表R1所维护的LSI
R1的LSI | R2的LSI | R3的LSI | R4的LSI | 备注 | ||
Router ID | 10.1.1.1 | 10.1.1.2 | 10.1.1.5 | 10.1.1.6 | 标识路由器的IP地址 | |
Link1 | ID | 10.1.1.2 | 10.1.1.1 | 10.1.1.6 | 10.1.1.5 | 所连路由器的RounterID |
IP | 10.1.1.1 | 10.1.1.2 | 10.1.1.5 | 10.1.1.6 | Link1的基本IP地址 | |
Metric | 3 | 3 | 6 | 6 | Link1的费用 | |
Link2 | ID | 10.1.1.5 | 10.1.1.6 | 10.1.1.1 | 10.1.1.12 | 所连路由器的RounterID |
IP | 10.1.1.9 | 10.1.1.13 | 10.1.1.10 | 10.1.1.14 | Link2基本IP地址 | |
Metic | 2 | 4 | 2 | 4 | Link2费用 | |
Net1 | Prefix | 192.1.1.0/24 | 192.1.6.0/24 | 192.1.7.0/24 | 192.1.7.0/24 | 直接网络Net1的网络前缀 |
Metric | 1 | 1 | 1 | 1 | 到达直连网络Net1的费用 |
题42图 R1构造的网络拓扑
请回答下列问题。
(1) 本题中的网络可抽象为数据结构中的哪种逻辑结构?
(2) 针对题42表中的内容,设计合理的链式存储结构,以保存题42表中的链路状态信息(LSI)。要求给出链式存储结构的数据类型定义,并画出对应题42表的链式存储结构示意图(示意图中可仅以ID标识节点)。
(3) 按照迪杰斯特拉(Dijikstra)算法的策略,依次给出R1到达题42图中子网192.1.x.x的最短路径及费用。