SCTP 协议实战：基于 UNPv1 第3版 实现多流回射服务器，解决 TCP 头端阻塞
2026/7/13 6:34:34
核心定义
在一个图（由节点和边组成）中，最短路径是指从起点到终点，所有可行路径里，边的某种权重总和最小的那一条。
单源最短路径--Dijkstra算法
从起点开始，每次从未确定最短路径的顶点中，选择距离起点最近的一个，将其标记为“已确定”，然后尝试用该顶点去“松弛”它的邻居节点。
核心流程
初始化：起点
s到自身的距离为0，到其他所有顶点的距离为∞（无穷大）。所有顶点均为“未访问”。选择：从“未访问”顶点中，选出当前距离值最小的顶点
u（第一次选出的就是起点）。标记：将
u标记为“已访问”（即该顶点的最短路径已确定）。松弛：遍历
u的所有邻居v。如果dist[u] + weight(u, v) < dist[v]，则更新dist[v]为更小的值。循环：重复步骤 2-4，直到所有顶点都被访问（或者目标顶点被访问，可提前终止）。
形象比喻：像水流扩散，从源点像水波一样一圈圈往外推。
正确执行流程示例
假设邻接矩阵：
A B C D
A 0 1 4 ∞
B ∞ 0 2 5
C ∞ ∞ 0 1
D ∞ ∞ ∞ 0
从A出发（srci=0）：
初始：
dist=[0, ∞, ∞, ∞]，S=[F,F,F,F]第1轮：选A（u=0），
S[0]=T。松弛B(1)、C(4) →dist=[0,1,4,∞]第2轮：选B（dist=1），
S[1]=T。松弛C(1+2=3<4 → 更新为3)、D(1+5=6) →dist=[0,1,3,6]第3轮：选C（dist=3），
S[2]=T。松弛D(3+1=4<6 → 更新为4)第4轮：选D（dist=4），
S[3]=T。结束
最终dist=[0,1,3,4]，pPath=[0,0,1,2]（表示A→B→C→D）
代码实现
1.函数签名与参数
void Dijkstra(const V& src, vector<W>& dist, vector<int>& pPath)src：起点顶点
dist：输出参数，存储起点到每个顶点的最短距离pPath：输出参数，存储每个顶点的前驱节点（用于回溯最短路径）
2.初始化阶段
size_t srci = GetVertexIndex(src); // 将顶点转为数组下标 size_t n = _vertexs.size(); // 顶点总数 dist.resize(n, MAX_W); // 所有距离初始为"无穷大" pPath.resize(n, -1); // 前驱初始为-1（无前驱） dist[srci] = 0; // 起点到自身距离为0 pPath[srci] = srci; // 起点的前驱设为自己（路径终点标记） //已经确定最短路径的顶点集合 vector<bool> S(n, false); // S[i]=true表示顶点i已确定最短路径MAX_W是预设的极大值（如INT_MAX），表示不可达S集合是Dijkstra贪心策略的核心：已选入的顶点其最短路径不会再改变
3.主循环（选点 + 松弛）
for (size_t count = 0; count < n; count++) // 循环n次，每次确定一个顶点 { // 1. 选点：从S集合外选dist最小的顶点u int u = -1; W min = MAX_W; for (size_t i = 0; i < n; i++) { if (!S[i] && dist[i] < min) { u = i; min = dist[i]; } } if (u == -1) break; // 剩余顶点不可达，提前结束 S[u] = true; // 将u加入已确定集合 // 2. 松弛：用u去更新它的所有邻居v for (size_t v = 0; v < n; v++) { if (!S[v] && _matrix[u][v] != MAX_W && dist[u] + _matrix[u][v] < dist[v]) { dist[v] = dist[u] + _matrix[u][v]; pPath[v] = u; // 记录前驱：到v的最短路径经过u } } }Dijkstra算法只能用来解决正权图的单源最短路径问题，但有些题目会出现负权图。这时这个算法
就不能帮助我们解决问题了，而bellman—ford算法可以解决负权图的单源最短路径问题。
单源最短路径--Bellman-Ford算法
核心思想
与Dijkstra的贪心策略不同，Bellman-Ford采用动态规划思想：
对每条边进行V-1轮松弛操作（V为顶点数）
每轮尝试用所有边去更新距离
第k轮结束后，得到的是最多经过k条边的最短路径
形象比喻：像"消息传递"，每一轮信息沿着边走一步，经过 n-1 步后信息能到达所有可达节点。
算法流程总结
Bellman-Ford算法执行流程：
1. 初始化：
dist[srci] = 0, 其余为∞
pPath[srci] = srci, 其余为-1
2. 主循环 (k = 0 to V-2)：
├─ 遍历所有边 (i→j)
│ └─ 如果 dist[i] + weight(i,j) < dist[j]
│ ├─ dist[j] = dist[i] + weight(i,j)
│ └─ pPath[j] = i
├─ 如果本轮无更新 → 提前终止
└─ 继续下一轮
3. 负环检测：
├─ 再次遍历所有边
│ └─ 如果还能松弛 → 存在负环，返回false
└─ 返回true（求解成功）
4. 结果：
dist数组存储最短距离
pPath数组存储路径前驱
代码实现
1.函数签名与初始化
bool BellmanFord(const V& src, vector<W>& dist, vector<int>& pPath)参数：
src：源点（起点）dist：输出参数，存储源点到各顶点的最短距离pPath：输出参数，存储最短路径树中每个顶点的父节点（用于回溯路径）
返回值：
true表示成功找到最短路径，false表示存在负权回路（此时最短路径无意义）
size_t n = _vertexs.size(); size_t src_i = GetVertexIndex(src); dist.resize(n, MAX_W); pPath.resize(n, -1); dist[srci] = W(); // 源点到自身距离为0（W()是默认构造，通常为0）2.核心松弛操作（外层循环 n-1 轮）
for (size_t k = 0; k < n - 1; ++k) { //i->j 更新松弛 bool update = false; for (size_t i = 0; i < n; ++i) { for (size_t j = 0; j < n; ++j) { // srci->i + i->j < srci->j 则更新路径及权值 if (_matrix[i][j] != MAX_W && dist[i] + _matrix[i][j] < dist[j]) { update = true; dist[j] = dist[i] + _matrix[i][j]; pPath[j] = i; } } } //如果这个轮次中没有更新出最短路径，那么后续轮次就不需要再走了 if (update == false) break; }松弛操作：如果通过顶点
i到达j比当前记录的dist[j]更短，就更新为什么是 n-1 轮：在无负权回路的情况下，最短路径最多包含 n-1 条边（因为n个顶点的简单路径最多n-1条边），经过 n-1 轮松弛，一定能得到所有顶点的最短路径
优化：
update标志记录本轮是否有更新，如果没有更新，提前退出
3.检测负权回路
for (size_t i = 0; i < n; i++) { for (size_t j = 0; j < n; j++) { if (_matrix[i][j] != MAX_W && dist[i] + _matrix[i][j] < dist[j]) { return false; } } } return true;为什么能检测负权回路：
经过 n-1 轮松弛后，所有顶点的最短距离已经确定
如果再进行一轮松弛还能更新（
dist[i] + weight < dist[j]），说明存在一个可以无限降低路径长度的负权回路此时返回
false表示无解（最短路径不存在）
多源最短路径--Floyd-Warshall算法
Floyd-Warshall算法是一种动态规划算法，用于在带权有向图或无向图中，求出所有点对之间的最短路径。
核心思想
逐步允许更多的顶点作为“中转站”，不断松弛所有点对之间的距离。
形象比喻：像逐步开通新的高速公路枢纽，每次新开一个枢纽，就检查所有城市对是否可以通过这个枢纽走得更短。
解释：
一开始，我们认为任意两点之间只能直达（或者不通）。
然后，我们逐个解锁顶点：
第 1 步：允许经过顶点 1 中转
第 2 步：允许经过顶点 1、2 中转
…
第 k 步：允许经过顶点 1..k 中转
每解锁一个顶点，就检查：从 i 到 j 走“旧路”更短，还是绕道新解锁的 k 更短，取最小值。
代码实现
1.函数签名与变量含义
FloydWarshall(vector<vector<w>> & vvDist, vector<vector<int>> & vvpPath)- vvDist：最短路径距离矩阵，最终
vvDist[i][j]= i→j 的最短路径长度 - vvpPath：最短路径前驱矩阵，用于重建完整路径
2.初始化阶段
- 获取顶点数并 resize
_vertexs是类成员，存储所有顶点，n为顶点个数。
size_t n = _vertexs.size(); vvDist.resize(n); vvpPath.resize(n);- 每个矩阵的行 resize
for (size_t i = 0; i < n; ++i) { vvDist[i].resize(n, MAX_W); // 默认所有距离为无穷大 vvpPath[i].resize(n, -1); // 默认路径为 -1（无前驱） }- 用图的原始边填充矩阵
for (size_t i = 0; i < n; ++i) { for (size_t j = 0; j < n; ++j) { // 如果有直接边 i→j if (_matrix[i][j] != MAX_W) { vvDist[i][j] = _matrix[i][j]; // 距离 = 边权 vvpPath[i][j] = i; // 前驱是 i（直接从 i 到 j） } // 自己到自己距离为 0，前驱为 -1 if (i == j) { vvDist[i][j] = 0; vvpPath[i][j] = -1; } } }vvpPath[i][j] = i的含义：
表示在初始状态下，从 i 到 j 的路径倒数第二个顶点是 i（即直接从 i 出发一步到 j）。
3.核心三重循环更新
for (size_t k = 0; k < n; ++k) // 中转点 { for (size_t i = 0; i < n; ++i) // 起点 { for (size_t j = 0; j < n; ++j) // 终点 { // 条件：i→k 可达 且 k→j 可达 if (vvDist[i][k] != MAX_W && vvDist[k][j] != MAX_W && vvDist[i][k] + vvDist[k][j] < vvDist[i][j]) { vvDist[i][j] = vvDist[i][k] + vvDist[k][j]; vvpPath[i][j] = vvpPath[k][j]; // ⭐ 重点！ } } } }重点解释：vvpPath[i][j] = vvpPath[k][j]
这是路径更新的核心，会疑惑为什么不是= k。
假设我们找到了更短路径：
i → ... → k → ... → j
更新后的路径是：i 到 k 的最短路径+k 到 j 的最短路径。
整个路径的倒数第二个顶点，其实就是k→j 路径的倒数第二个顶点，也就是vvpPath[k][j]。
最外面一层循环的作用：
举个例子：
图的基本信息
边的信息（有向图）
| 起点 | 终点 | 权值 |
|---|---|---|
| S | A | 3 |
| S | B | 10 |
| A | C | 2 |
| B | C | 1 |
| C | D | 4 |
| D | T | 2 |
邻接矩阵_matrix（行 → 列）
| 行列 | 0(S) | 1(C) | 2(T) | 3(A) | 4(D) | 5(B) |
|---|---|---|---|---|---|---|
| 0(S) | 0 | ∞ | ∞ | 3 | ∞ | 10 |
| 1(C) | ∞ | 0 | ∞ | ∞ | 4 | ∞ |
| 2(T) | ∞ | ∞ | 0 | ∞ | ∞ | ∞ |
| 3(A) | ∞ | 2 | ∞ | 0 | ∞ | ∞ |
| 4(D) | ∞ | ∞ | 2 | ∞ | 0 | ∞ |
| 5(B) | ∞ | 1 | ∞ | ∞ | ∞ | 0 |
唯一的一轮循环
| 步骤 | i (起点) | dist[i] | 能更新的 j | 结果 |
|---|---|---|---|---|
| 1 | i=0 (S) | 0 | j=3 (A): 0+3=3 < ∞ j=5 (B): 0+10=10 < ∞ | dist[A]=3 dist[B]=10 |
| 2 | i=1 (C) | ∞ | 无法更新 | 无变化（还没到达 C） |
| 3 | i=2 (T) | ∞ | 无法更新 | 无变化 |
| 4 | i=3 (A) | 3 | j=1 (C): 3+2=5 < ∞ | dist[C]=5 |
| 5 | i=4 (D) | ∞ | 无法更新 | 无变化（还没到达 D） |
| 6 | i=5 (B) | 10 | j=1 (C): 10+1=11 < 5? 不成立 | 不变（C 已有更短 5） |
单轮循环结束时的 dist
dist = [0, 5, ∞, 3, ∞, 10]
S C T A D B
结果：T 和 D 仍然是 ∞！✖
为什么最后导致dsti[d]仍然是无穷 按理来说应该可以走S->A->C->D这条路径
因为当没有最外层循环时 当矩阵遍历到第四层 （i=3）也就是A这一层时 才拿到A->C这条路径值 而C这层是i=1 当遍历i=1这层时dsti只记录了A,B为终点的值 即使遍历到了C->D这条路径也无法得知dsti[d]的值 因为缺少S->C这条路径的值 也就是没有dsti[c] 所以C->D这条路径值丢失了 等到第四层时即使有了dsti[c]也无法从头去获得C->D这条路径值
这正好说明了Floyd-Warshall 需要完整的 n 轮循环，并且k 必须按顺序在最外层的原因。
对比Dijkstra、Bellman-Ford和Floyd-Warshall这三种最短路径算法
| 对比维度 | Dijkstra | Bellman-Ford | Floyd-Warshall |
|---|---|---|---|
| 类型 | 单源最短路径 | 单源最短路径 | 全源最短路径 |
| 适用图 | 有向图/无向图 | 有向图/无向图 | 有向图/无向图 |
| 边权 | 非负权 | 可负权 | 可负权 |
| 负权环 | 不支持 | 能检测 | 能检测 |
| 时间复杂度 | O(n²) 或 O(m log n) | O(n·m) | O(n³) |
| 空间复杂度 | O(n) | O(n) | O(n²) |
| 核心思想 | 贪心 | 动态规划/松弛 | 动态规划 |