题目内容

网络中有 $n$ 台路由器 $R1,R2,...,Rn$，两台路由器之间最多只有一条链路双向连通，每条链路有对应的转发成 本 $Lij(Lij>0,Lij=Lji)$ 。以 $Ri$ 为源节点进行转发时，会以 $Ri$ 为根基于链路转发成本计算一棵最短路径树，$Ri$ 到其它 $Rj$ 的报文会沿着最短路径树进行转发。以下图拓扑为例，$R1$ 到 $R2$ 的最短路径为 $R1->R2$ ，最小转发代价为 $5$ (所有路径成本之和).

转发的下一跳定义如下: 源节点 $S$ 到目的节点 $D$ 的最短路径上 $S$ 的直连的邻居节点，用来指导报文从哪条链路转发。以下图为例，$R1$ 到 $R2$ 的转发下一跳为 $R2$ 。

需要注意的是，最短路径树中最短路径可能不止一条，对应转发的下一跳可能存在多个。以下图为例，$R1$ 到 $R3$ 的最短路径有两条,分别为: $R1->R2->R3;R1->R4->R3$,$R1$ 到 $R3$ 的转发下一跳为 $R2、R4$ 。