最短路

最短路算法旨在寻找图中两点间总权重最小的路径，它是图论领域的核心问题。不同算法因其独特策略，适用于各异的场景。

对于不含负权边的图，Dijkstra算法是经典选择。它采用贪心策略，从起点逐步向外扩展，每次确定一个当前最短距离的顶点。通过优先队列优化，它能实现很高的效率，是网络路由等实际应用中最常用的算法。

当图中存在负权边时，Bellman-Ford算法则展现出其不可替代的价值。它通过持续松弛所有边来逐步逼近最优解。虽然效率不及Dijkstra，但其独特优势在于能检测出图中存在的负权回路，这是其他算法无法做到的。

而对于需要计算所有点对间最短路的场景，Floyd算法提供了最直接的方案。它基于动态规划思想，通过中间节点系统地更新所有点对间的距离。其思想简洁，实现容易，成为解决全局最短路问题的有力工具。

这些算法共同构成了解决最短路问题的工具箱，其核心思想——松弛操作，是它们高效求解的共同基石。

排列组合是研究事物在特定规则下安排与选择方式的数学分支，构成了计数问题的理论基础。排列关注元素的有序安排，从 $n$ 个不同元素中取 $m$ 个的排列数为 $P(n, m) = \frac{n!}{(n-m)!}$，它强调了顺序不同即为不同方案；而当元素可重复时，排列数变为 $n^m$。组合则关注元素的无序选择，组合数 $C(n, m) = \frac{n!}{m!(n-m)!}$ 体现了“选择哪些元素”而不关心其顺序的核心思想。

在实际应用中，需要灵活运用加法原理（分类计数）和乘法原理（分步计数），并熟练掌握隔板法、捆绑法、容斥原理等技巧处理复杂约束。排列组合不仅是概率计算的基础，在算法分析、密码学、优化调度等领域都有重要应用，其思维方式训练了我们系统分析问题的能力，避免枚举时重复或遗漏，实现精确高效的计数。

【前置知识点】
1、广度优先搜索

【后置知识点】
1、并查集

【思维导图】

【题目知识点分类】