第四十四天
所花时间（包括上课）：约 8 小时（概率论 2.5h + 算法练习（最短路） 4h + 博客整理 1h + 其他 0.5h）
代码量（行）：约 320 行（主要为 Dijkstra 算法堆优化模板实现、Bellman-Ford 处理负权边逻辑编写及几道典型图论最短路题目的 AC 代码）
博客量（篇）：1 篇
了解到的知识点：
概率论与数理统计：几种重要离散随机变量的分布 —— 在掌握了期望与方差后，今天系统学习了三种核心离散分布：二项分布、泊松分布和几何分布。深入推导了二项分布的期望
很小时，二项分布可以用泊松分布作为近似，这在处理大规模随机事件（如网页访问量、车站流量）时极具实用价值。此外，还探讨了几何分布的“无记忆性”，这一直观上有些反直觉但在概率建模中非常重要的特性。
算法练习与沉淀：图论中的最短路算法（Shortest Path） —— 今天攻克了图论的核心内容：单源最短路算法。重点掌握了 Dijkstra 算法，尤其是结合 priority_queue 实现的堆优化版本（时间复杂度
O(mlog n)O(mlogn)，这在处理稀疏图时效率极高。随后学习了 Bellman-Ford 算法 及其改进版 SPFA，深刻理解了它们在处理包含负权边图时的优势，以及如何利用它们判定图中是否存在负环。在练习中，我发现图论题目最大的挑战在于建图（邻接矩阵 vs 邻接表）以及对“松弛操作（Relaxation）”本质的理解。
总结：
今天的学习呈现出明显的“从局部到整体”的特征。概率论中，从单个随机变量的属性延伸到了经典的概率分布模型，这让我意识到数学建模就是寻找现实问题与这些标准分布之间的契合点。在算法方面，最短路问题是我之前一直比较敬畏的领域，但通过今天对 Dijkstra 算法的拆解，我发现其本质也是一种贪心策略。图论编程对细节的要求极高，一个数组大小的失误或初始化值的设定（如用 0x3f3f3f3f 代替 INT_MAX）都会直接导致程序的崩溃。今晚在调试堆优化 Dijkstra 时，我花了很多时间理清“入队次数”与“出队更新”的关系，深刻体会到图论中“状态标记”的重要性。
表 3 缺陷记录日志示例
学生：马昀昀_________
日期：5.13_______
程序号：算法练习-单源最短路（堆优化 Dijkstra 模板）
编号：2
类型：20 （注：PSP标准中20代表逻辑/控制/条件错误）
引入阶段：编码
排除阶段：测试
修复时间：25min
修复缺陷：
描述：在实现堆优化版本的 Dijkstra 算法时，程序在处理较大规模数据时运行结果不正确，且存在大量重复计算。通过断点调试发现，我在使用优先队列 priority_queue<pair<int, int>> 时，由于 C++ 默认是大顶堆（Max-Heap），而算法要求每次取出距离最小的点，我没有正确处理优先级。此外，在点出队后，我遗漏了判断当前出队距离是否大于 dist[u] 的步骤，导致已经被处理过的、具有更短路径的点被重复且无效地用于松弛其他边。
修复方法：首先，将优先队列改为小顶堆，即 priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>（或者在入队时将距离取负值值）。其次，在 pop() 出队后立即加入 if (d > dist[u]) continue; 的剪枝逻辑，确保每个节点只在其最短路径真正确定时才进行一次松弛操作。修复后，程序在复杂拓扑图下的运行效率显著提升，并顺利通过所有测试点。
