图搜索算法

Dijkstra 算法

参考
Dijkstra 只能用在权重为正的图中，因为计算过程中需要将边的权重相加来寻找最短路径。

对于图 $G=\langle V,E\rangle$ 上带权的单源最短路径问题, Dijkstra 算法通过保留目前为止所找到的每个顶点 $v\in V$ 从 $s$ 到 $v$ 的最短路径来工作。

算法维护两个顶点集合 $S$ 和 $Q$。集合 $S$ 保留所有已知实际最短路径值的顶点，而集合 $Q$ 则保留其他所有顶点。

1. 集合 $S$ 初始状态为空。初始时，原点 $s$ 的路径长度 $d[s]=0$, 所有其他顶点的路径长度 $d[u]=+\infty$。每个点的最小路径数列 $l[u]=[\varnothing]$。
2. $Q$ 中拥有最小的 $d[u]$ 值的顶点从 $Q$ 移动到 $S$。
3. 对 $u$ 的每条 $v\notin S$ 的外接边 $w(u,v)$ 进行松弛。
   1. 松弛操作(relaxation)：$d’[v]=d[u]+w(u,v)$, $l’[v]=l[u]+[u]$。如果 $d’[v]<d[v]$，则 $d[v]=d’[v]$, $l[v]=l’[v]$。
4. 重复步骤 2 和 3，直到 $t\in S$。$l[t]$ 中存储的便是从 $s$ 到 $t$ 的最短路径，或者如果路径不存在的话是无穷大。

Floyd 算法 TODO

参考
可以正确处理有向图或负权（但不可存在负权回路）的最短路径问题

A*算法

参考
在 Dijkstra 算法的基础上, 增加了启发式函数 $h(u)$, 用来估计当前节点到目标节点的距离。即 $f(u)=d(u)+h(u)$, 其中 $d(u)$ 是从 $s$ 到 $u$ 的距离, $h(u)$ 是从 $u$ 到 $t$ 的估算距离。

1. 集合 $S$ 初始状态为空。初始时，原点 $s$ 的路径长度 $d(s)=0, f(s)=h(s)$, 所有其他顶点的路径长度 $d(u)=+\infty$。每个点的最小路径数列 $l(u)=[\varnothing]$。
2. $Q$ 中拥有最小的 $f(u)$ 值的顶点从 $Q$ 移动到 $S$。
3. 对 $u$ 的每条 $v\notin S$ 的外接边 $w(u,v)$ 进行松弛。
   1. 松弛操作(relaxation)：$d’(v)=d(u)+w(u,v)$, $l’(v)=l(u)+[u]$。如果 $d’(v)<d(v)$，则 $d(v)=d’(v)$, $l(v)=l’(v)$, $f(v)=d(v)+h(v)$。
4. 重复步骤 2 和 3，直到 $t\in S$。$l(t)$ 中存储的便是从 $s$ 到 $t$ 的最短路径，或者如果路径不存在的话是无穷大。

Prim 算法

最小生成树算法
参考, 参考

1. 输入: 一个加权连通图, 其中定点集合为 $V$, 边集合为 $E$
2. 初始化: $V_{new}={x}$, $E_{new}=\varnothing$, $x$ 为 $V$ 中的任一节点(起始点)
3. 重复下列操作, 直到 $V_{new}=V$:
   1. 在 $E$ 中选取权值最小的边 $(u,v)$, 其中 $u$ 为 $V_{new}$ 中的元素, 而 $v$ 则为 $V-V_{new}$ 中的元素
   2. 将 $v$ 加入 $V_{new}$, 将 $u,v$ 加入 $E_{new}$
4. 输出: 使用集合 $V_{new}$ 和 $E_{new}$ 来描述所得到的最小生成树

Kruskal 算法

最小生成树算法
参考

1. 新建图 $G$, $G$ 中拥有原图中相同的节点，但没有边
2. 将原图中所有的边按权值从小到大排序
3. 从权值最小的边开始，如果这条边连接的两个节点于图 $G$ 中不在同一个连通分量中，则添加这条边到图 $G$ 中
4. 重复 3，直至图 $G$ 中所有的节点都在同一个连通分量中

KMP 算法 TODO

Bloom Filter TODO