技术部寒假第二次培训(最短路)

路径的概念

• 途径 (walk)：途径是连接一连串顶点的边的序列，可以为有限或无限长度。形式化地说，一条有限途径 是一个边的序列，使得存在一个顶点序列 满足 ，其中 。这样的途径可以简写为 。通常来说，边的数量 被称作这条途径的 长度（如果边是带权的，长度通常指途径上的边权之和，题目中也可能另有定义)。
• 迹 (trail)：对于一条途径 ，若两两互不相同，则称 是一条迹。
• 路径 (path)（又称 简单路径 (simple path)）：对于一条迹 ，若其连接的点的序列中点两两不同，则称 是一条路径。

单源最短路

Dijkstra算法

算法流程：

1. 初始化，其余结点的值为正无穷大。
2. 找出一个未被标记的、最小的结点，然后标记结点。
3. 扫描结点的所有出边，若，则使用更新。
4. 重复上述2~3的步骤，直到所有结点都被标记。

算法描述：

​ Dijkstra算法基于贪心思想，他只适用于所有边的长度都是非负数的情况。当边长都是非负数时，全局最小值不可能再被其他结点更新，故在第一步中选出的结点必定满足：已经是起点到的最短路径。我们不断选择全局最小值进行标记和扩展，最终可以得到起点1到每个结点的最短路径长度。

​ 给定一张有向图，若对于图中的某一条边 ，有成立，则称该边满足三角形不等式。若所有边都满足三角形不等式，则数组就是所求的最短路。

Bellman-Ford算法

​ 基于迭代思想的Bellman-Ford算法流程如下：

1. 扫描所有边，若，则用更新。
2. 重复上述操作，直到所有边都满足三角形不等式(n次就够了)。

该算法的时间复杂度为，其实我们发现这个算法中我们每次扫描都是扫描所有的边，会做很多无用功，我们其实可以想想证明优化它。

Bellman-Ford算法队列优化——SPFA算法

​ 我们发现只有在上一轮扫描中被松弛过的点才有可能更新其他点，所以我们可以用队列维护一下待扩展的点。每次入队相当于完成一次数组的更新操作，使其满足三角形不等式。一个结点可能会入队出队多次。最终，图中所有结点收敛到完全满足三角形不等式的状态。我们来看看SPFA的算法流程：

1. 建立一个队列，最初队列中只含有起点1。
2. 取出队头结点，扫描它的所有出边，若，则更新。同时若不在队列中，则把入队。
3. 重复上述步骤直到队列为空。

综合运用

J-旅行_图论基础 (nowcoder.com)

K-[NOIP2009 / 蓝书] 最优贸易_图论基础 (nowcoder.com)

N-[蓝书] 道路和航线_图论基础 (nowcoder.com)

M-小雨坐地铁_图论基础 (nowcoder.com)

多源最短路

Floyd算法

​ 设 表示“经过若干个编号不超过的结点” 从 到 的最短路长度。该问题可以划分为两个子问题，经过编号不超过 的结点从 到 ，或者从 先到 再到 。于是：

$$D[k,i,j] = min(D[k-1,i,j],D[i,k]+D[k,j])$$

​ 初值为 .

​ 可以看见，Floyd算法本身就是动态规划。 是阶段，所以必须置于最外层循环中。 和 是附加状态，所以应该置于内层循环。与背包问题的状态转移方程类似， 这一维可以被省略，最初我们可以直接用 来存邻接矩阵，然后执行动态规划过程。当外层循环到时，内层的状态转移

$$D[i,j] = min(D[i,j],D[i,k]+D[k,j])$$

​ 最终就保存了 到 的最短路长度。

传递闭包

​ 在交际网络中，给定若干个元素和若干对二元关系，且关系具有传递性。“通过传递性推导出尽量多的元素之间的关系”的问题被称为传递闭包。

例题及简单变形

Q-[蓝书] Sorting It All Out_图论基础 (nowcoder.com)

看到群里有打牛客周赛的结果，讲一下快速幂、质因数分解，有时间再讲讲乘法逆元