链路状态路由算法C++实现：邻接矩阵与Dijkstra最短路径详解

简介这份文档面向计算机网络课程学习者与路由算法入门者系统讲解链路状态路由算法的原理与实现帮助读者理解自治系统内部路由选择的核心机制。内容围绕发现邻接点、测量链路开销、构造并传播链路状态分组、更新拓扑视图、计算最短路径五个基本步骤展开并给出基于Dijkstra算法的C实现示例涵盖邻接矩阵初始化、路由表创建与保存、节点增删等辅助函数便于对照代码理解算法流程。资源包为单个docx文档压缩后约263KB结构紧凑适合作为课堂笔记补充或实验参考。目前已有124人学习内容兼顾理论推导与代码实践可帮助读者掌握从全网拓扑构建到最短路径求解的完整思路并了解该算法在OSPF等域内路由协议中的实际应用价值。1. 链路状态路由算法拆包从邻接矩阵到 Dijkstra 最短路径的完整 C 实现带过计算机网络课的人多半在 OSPF 那一章背过“链路状态”四个字但真让你手写一个能跑的路由计算程序很多人会卡在邻接矩阵怎么建、Dijkstra 的松弛条件怎么写、路由表怎么存盘这几个具体环节上。这份《链路状态路由算法.docx》给的不是纯理论讲义而是一套能编译、能交互、能落盘的 C 源码核心就是邻接矩阵加 Dijkstra 最短路径。它适合两类人一类是正在做路由算法课程设计、需要一份可运行参考实现的学生另一类是想借这个小程序把 Dijkstra 从伪代码落到真实数组操作上的开发者。下面我按“原理立住 → 代码跑通 → 坑排掉 → 进阶验证”的顺序把这份资源拆开讲透。2. 链路状态路由原理与邻接矩阵建模为什么选 Dijkstra 而不是 Bellman-Ford2.1 链路状态算法的五个基本步骤链路状态路由协议是目前使用最广的一类域内路由协议它的设计策略可以理解成“拼图”每台路由器把自己到周围邻居的链路状态向全网广播每台路由器收到其他路由器发来的信息后对这些链路状态进行拼装最终生成一张全网的拓扑视图再通过最短路径算法计算自己到其他路由器的最短路径。运行链路状态协议的路由器只在接口状态发生变化时才把变化后的状态发给其他所有路由器每台路由器用收到的信息重新计算前往每个网络的最佳路径并存入自己的路由选择表。这套思想可以用五个基本步骤描述第一发现邻接点并知道其网络地址第二测量到各邻接点的延迟或开销第三构造一个包含刚收到信息的分组第四把这个分组发送给其他路由器第五计算出到每一个其他路由器的最短路径。这份资源里的 C 程序重点落在第五步——用 Dijkstra 算法从邻接矩阵里算出最短路径。2.2 邻接矩阵把网络拓扑压进二维数组程序用dist[MAX_NODES][MAX_NODES]这个二维数组存放网络拓扑的连接矩阵dist[i][j]表示节点 i 到节点 j 的链路权值0 表示不直接相连。Vnums是全局的总节点数INFINITY取 100000 作为“不可达”的替代值。这里有个设计取舍值得说用固定大小的二维数组而不是邻接表好处是 Dijkstra 里查任意两点权值都是 O(1)代码直观代价是节点数受MAX_NODES 1024限制且稀疏图会浪费大量空间。对于课程设计和中小规模拓扑演示这个取舍是合理的。初始化函数initDist()把整个矩阵清零creatRouteMap()则按用户输入逐个填充权值。注意它填充时是让用户对每个 i、j 都输入一遍实际使用时如果图是无向的应该保证dist[i][j] dist[j][i]这一点在后面的增删改函数里有体现但创建函数本身没有强制对称这是第一个要留神的地方。2.3 为什么核心算法选 Dijkstra链路状态路由的经典配套算法就是 Dijkstra因为每台路由器手里有全网拓扑属于“全局已知”场景正好适合 Dijkstra 这种从源点出发、每次确定一个最近节点的贪心策略。相比之下 Bellman-Ford 更适合分布式、逐跳交换距离向量的场景。这份源码里dijkstra(int s, int t, int path[])的形参命名有点绕注释写的是“s 目的节点 t 源节点”但函数体里state[t].length 0把 t 当源点初始化while(k!s)又以 s 为终止目标。也就是说实际语义是 t 为源、s 为目的和形参注释相反。读代码时以函数体为准别被注释带偏这是第二个要标记的坑。3. 编译与运行实操从源码到 routeTable.txt 的完整流程3.1 环境准备与编译命令这份源码只依赖iostream和fstream没有第三方库标准 C 环境即可编译。Windows 下用 MinGW 或 Visual Studio 都行Linux/macOS 用 g 直接编。常见做法是# 把源码保存为 linkstate.cpp g -stdc11 -O2 -o linkstate linkstate.cpp # 运行 ./linkstate-stdc11是为了兼容代码里可能用到的初始化写法-O2开优化-o指定输出可执行文件名。如果你在 VS Code 里配 C/C 环境记得把 tasks.json 的 compilerPath 指向你的 g否则会出现“函数变量无法跳转”这类配置问题那多半是 IntelliSense 没配好和源码本身无关。3.2 主菜单八个功能逐项说明程序启动后先要求输入路由总节点数然后进入一个循环菜单八个选项分别是创建路由表、增加路由、删除路由、修改路由、找两个路由间的最短路径、保存路由表到文件、显示路由表信息、退出。这个菜单结构对应了路由表的全生命周期管理下面挑关键几个讲。创建路由表走creatRouteMap()它会提示“输入第 i 个节点的第 j 个节点的权值”你需要把整个邻接矩阵填一遍。以资源里给出的拓扑为例节点用 A、B、C、D、E、F 表示对应数字 0 到 5边权分别是 2、3、3、6、1、5、7、8 这类值。填的时候对角线填 0不相连的填 0。// creatRouteMap 核心逻辑双重循环读入邻接矩阵 for(int i 0; i Vnums; i ){ cout 输入第 i 个节点\n; for(int j 0; j Vnums; j ){ cout 的第 j 个节点的权值; cin dist[i][j]; // dist[i][j] 即 i 到 j 的链路开销 } }这里Vnums是全局变量创建时按当前节点数遍历。参数含义很直接外层 i 是行源内层 j 是列目的cin读入的每个值就是这条链路的开销。注意如果两个节点不直接相连要填 0 而不是INFINITY因为 Dijkstra 里判断相连的条件是dist[k][i] ! 0。3.3 Dijkstra 求最短路径的调用方式选菜单 5 后程序提示“输入目标节点和源节点”先读desNode再读rouNode然后调用dijkstra(desNode, rouNode, path)。结合前面说的形参语义第一个实参desNode实际被当作目的节点 s第二个rouNode被当作源节点 t。所以输入顺序是“先目的、后源”和直觉相反。比如你想算从节点 0 到节点 5 的最短路径应该先输 5 再输 0。这个顺序坑我在第一次跑的时候也翻过车输出结果对不上回头读函数体才发现。// 菜单 5 的调用片段 case 5: cout 输入目标节点和源节点 endl; cin desNode; // 实际作为 dijkstra 的目的节点 s cin rouNode; // 实际作为 dijkstra 的源节点 t dijkstra(desNode, rouNode, path); system(pause); system(cls); break;3.4 路由表保存与文件输出选菜单 6 会把当前邻接矩阵写入routeTable.txt文件名由宏#define routeTable routeTable.txt定义。saveRoute()先写一行“路由邻接矩阵为”再写分隔线然后逐行逐列输出矩阵列间用制表符\t对齐。打开文件时用ofstream如果routeTables NULL就报“打开文件夹错误”并退出。这里有个小瑕疵判断流是否成功应该用!routeTables.is_open()或!routeTables用 NULL在标准流对象上语义不严谨但多数编译器能过。// saveRoute 输出格式 routeTables 路由邻接矩阵为\n; routeTables **********************************\n; for(int i 0; i Vnums; i ){ for(int j 0; j Vnums; j ){ routeTables dist[i][j] \t; // 制表符分隔便于对齐 } routeTables \n; }保存下来的文件可以直接当实验报告里的“路由表输出”截图替代品也方便你下次运行时对照检查矩阵是否填错。4. 避坑与排查Dijkstra 实现里最容易翻车的五个点4.1 现象最短路径结果比实际大很多原因邻接矩阵里不相连的边填了 0但 Dijkstra 松弛时判断条件是dist[k][i] ! 0如果某条本该相连的边你误填成 0算法会认为它不相连直接跳过导致绕远路。解决创建矩阵时逐条核对相连边填真实权值不相连填 0对角线也填 0。跑之前先用菜单 7 显示矩阵肉眼扫一遍对称性。4.2 现象程序输出“最短路径为”后路径断断续续原因dijkstra里输出k -是在松弛成功的分支里直接打印的它打印的是当前扩展节点不是最终路径序列。真正的路径要靠state[i].predecessor回溯但源码没有写回溯输出所以看到的箭头序列只是扩展顺序不是完整路径。解决如果需要完整路径在算法结束后从目的节点沿predecessor反向回溯到源点再倒序打印。这是这份源码最值得自己补的一块。4.3 现象删除路由后最短路径算出来还是老结果原因deleteRoute()把dist[delNum-1][j]和dist[j][delNum-1]都置 0但节点编号并没有真正从图里移除Vnums也没减。也就是说被删节点仍占着一个编号只是所有边断了。解决如果要做真正的节点删除需要把后续节点整体前移并Vnums--否则就接受“逻辑删除”的语义知道被删节点变成孤立点即可。4.4 现象修改权值后矩阵不对称原因changeRoute()只改了dist[i-1][j-1]一个方向没有同步改dist[j-1][i-1]。对于无向图这会导致 i 到 j 和 j 到 i 权值不一致Dijkstra 结果取决于你从哪个方向走。解决在changeRoute()里补一行dist[j-1][i-1] dist[i-1][j-1];保持对称。4.5 现象节点数超过 1024 直接崩溃原因MAX_NODES固定为 1024dist是静态二维数组超了就越界。解决课程设计规模一般远小于 1024不用管如果真要扩把MAX_NODES调大或改用vectorvectorint动态分配。另外INFINITY取 100000如果链路权值总和可能超过它松弛时会误判权值大时把它调成更大的值。5. 进阶验证用 predecessor 回溯完整路径并做正确性自检源码里state结构体的predecessor字段注释写着“父节点类似存下一跳”它记录的是每个节点在最短路径树上的前驱。算法跑完后从目的节点 s 出发反复取state[cur].predecessor直到回到源点 t就能还原完整路径。我一般会加一个独立函数做这件事顺便和state[s].length对拍验证路径长度和最小距离一致。// 在 dijkstra 末尾或单独函数里回溯路径 void printPath(int s, int t, state st[]){ // s 目的节点t 源节点st 为算法内部的 state 数组 int cur s; cout 完整路径(逆序): cur; while(cur ! t st[cur].predecessor ! -1){ cur st[cur].predecessor; cout - cur; } cout endl; // 自检累加路径权值应与 st[s].length 相等 }注意state目前是dijkstra函数内的局部结构体数组要在外部回溯就得把它提出来做参数或改成全局。参数说明s是目的节点t是源节点st[cur].predecessor为 -1 表示没有前驱即源点或不可达。自检时把路径上每条边的dist累加和state[s].length比对相等说明松弛过程没出错。验证方法上我习惯用资源里那张六节点拓扑做基准手工按 Dijkstra 表格推一遍每轮的距离向量再和程序输出对照。如果某一轮的最小距离对不上就回到 4.1 检查矩阵填值。另一个技巧是把routeTable.txt里的矩阵复制出来用 Python 的 networkx 或手写 Dijkstra 跑一遍两边结果一致才算过。这套流程走下来你对链路状态路由的理解就不再停留在背五个步骤而是能真正把邻接矩阵、松弛、前驱回溯这条链路串起来。从那以后我每次拿到最短路径相关的代码都强制先用小拓扑手工对拍一遍再上大图希望帮到你。本文还有配套的精品资源点击获取