恋上数据结构与算法（第二季）

《恋上数据结构与算法（第二季）》这一季的重心很明确：最短路径问题。具体落到三个经典算法——Dijkstra、Bellman-Ford、Floyd。如果你第一季已经过了数组、链表、栈队列、二叉树、堆、并查集这些结构，第二季就是把这些基础拼成一张能处理真实带权图的工具集；如果第一季是打地基，这一季开始盖楼，而且盖的是图论里最常被工程复用的那几层。

这一季到底在讲什么

三个算法看着都是"求最短路"，但适用边界完全不同，这也是这一季最值得对照实践的地方。Dijkstra 处理的是非负权单源最短路，核心是贪心加优先队列，工程里地图导航、网络路由的很多变体都从这里出发；Bellman-Ford 允许负权边，能顺带检测负环，代价是复杂度上到 O(VE)；Floyd 则是多源最短路，用三重循环做动态规划式的松弛，适合点集不大但要一次算出任意两点距离的场景。

把这三种放在一起学，价值不在于各自会写，而在于能判断"面对一张具体的图，我该选哪个"。这种判断力靠看视频看不出来，得自己拿数据跑一遍、对比一遍才会长在手上。

技术栈与代码形态

课程以 Java 为主要实现语言，沿用第一季建立的抽象习惯：图结构、边、顶点、权重的封装方式保持一致，算法实现建立在同一套接口之上。这意味着你在跟写时可以复用已有的图类，把注意力放在松弛操作、优先队列选点、距离数组更新这些真正的算法骨架上，而不是反复造图的数据结构。

这种组织方式对自学的意义在于：每个算法都是一个可独立编译、可替换输入的小模块。你可以把同一张测试图分别喂给三个实现，打印各自的距离矩阵做交叉验证——Floyd 的结果天然可以作为 Dijkstra 和 Bellman-Ford 的正确性参照。

可复用模块与练习路径

• 带权图的统一抽象：邻接表、邻接矩阵两种存储各自适配哪类算法，是后续所有实现的基础。
• 优先队列优化的 Dijkstra：理解为什么朴素 O(V²) 版本和堆优化版本在不同稠密度下各有胜场。
• Bellman-Ford 的迭代轮数与负环判定：第 V 次松弛仍能更新，就是负环存在的信号。
• Floyd 的三重循环顺序：为什么 k 必须放在最外层，这个细节写错了结果就悄悄不对。

建议的练习节奏是：每学完一个算法，先手写一遍不看参考，再对照课程实现找差异；然后自己构造边界用例——孤立点、零权边、负权边、含负环的图，看实现是崩溃、死循环还是给出合理结果。这几个用例比任何笔记都更能暴露理解漏洞。

适合谁，怎么用

这门课不适合零基础直接进。前置条件是能熟练写 Java、理解递归与基本复杂度分析，最好已经学过第一季的图基础部分。如果你是准备软考、或者面试里会被问到图论题，这三个算法几乎是必考项，而且面试官往往追问的不是"怎么写"，而是"为什么这样写""换种图还成立吗"。

使用方式上，把它当成一份可对照的参考实现来用，而不是被动看完的连续剧。边看边在本地建一个自己的图论小工程，把三个算法作为独立类放进去，配一套随机图生成器做压力测试。等你能不看资料讲清楚"Dijkstra 为什么不能处理负权边"，这一季就算真正吃透了。配套的章节笔记适合在动手之后回看，用来补上当时跳过的推导细节。