图论

最短路径朴素的dijkstra算法堆优化版的dijkstra算法bellman_ford 算法（带有负权边）spfa()算法 最小生成树朴素的prim算法kruskal算法

最短路径

朴素的dijkstra算法

找到不在集合内，距离一号点最近的点

1) dis[1] = 0, dis[others] = 正无穷 2） for(n次）{ 找到不在s中距离s最近的距离 将已经确定最短距离的点t放入集合s 用t更新其他点到起点的距离 }

堆优化版的dijkstra算法

bellman_ford 算法（带有负权边）

用一个点更新其他所有点的距离，所以可以求不超过k条边的最短路径 bellman_ford算法，可以求有限边的最短路。 求解含有负权边的单源汇最短路，但是效率有些低，使用的原理为用一个点对其他所有点进行松弛，每次松弛，将每条边都更新一下，如果可以在第n次还可以松弛，那么说明图中一定存在负环

算法步骤：

for(k次) for(a, b, w); d[b] = min(d[b], d[a] + w);

spfa()算法

用一个点更新其他所有点，用队列维护，更新后，存入变小的结点 可以说是对belloman_ford算法的bfs优化版本。 为了更快的求得最小距离，我们每次不在枚举所有的边，而是将所有可以更新距离的点更新距离，而这需用队列维护。

while (q.size(){//队列存上可以更新其他点的点 int t = q.front(); q.pop(); st[t];//表示不在队列里了。 for (遍历当前点可到达的点){ 更新点， 入队 标记入队 } }

---

最小生成树

朴素的prim算法

首先初始化diist全为正无穷 for (int i = 0; i < n; i ++){ 找到集合外距离集合最近的点。 用t更新其他点到集合的距离 把t放入st[t]为true }

kruskal算法

将所有边按照权重从小到大排序 枚举每条边a，b和权重c 如果a，b不连通，就将这条边加入集合内。