最小生成树(MST)：（针对于无向图）
—
定义n个顶点的图里面选n-1条边使得总边权和最小 或者选n-1边使得最大的边权最小，两种求法是相同的
最小生成树不是唯一的：
一个图分为树边(最小生成树的边)，和非树边，因为选择一个非树边跟树边构成一个环，如果里面的树边有大于等于非树边的就可以删除这条边，把非树边加入。 因此我们可以得出最小生成树唯一的充分条件是每一个非树边对应的环里的树边严格小于这条非树 边
—
prim算法证明：O(n2)
（反证法）假设最小的那条边不在最优解里面，那么一定可以从另一个方向连回来，构成一个环，删除的就不是最小的那条边了。
kruskal算法：mlogm (排序)
证明：（1）看两个点如果在一个集合里面，肯定不能加，会形成环
（2）（反证法）如果两个点不在一个集合里面假设没连，那么连到一起形成一个环，又因为没考虑过的边的权值一定比这条边的大，所以可以删除后连的，把这两个店形成的边加入进来

最短路：
1：单源最短路：dijkstra:本质是贪心，每次选择，距离起点距离最近的店。
证明，反正法，假设选择的不是最短的点，那么这个点一定可以被没被确定的点里面其他的点更新，由于边权都大于0，并且他已经是最短了，所以用其他点更新他的距离一定是大于他本身，所以不可能比他小
堆优化版本de dijkstra需要st数组，因为一个点可以有不同的距离多次入队，所以需要判重
st[]数组就是判断一个点的最短路是否被确定，dist[]是一个点到起点的距离st[]=1时dist才表示确定了最短路径。

dijkstrea更新的时候也可以，更新过的点，因为更新过的点永远不会被更新，因为已经确定最小距离
但是prim就不一样了，必须更新没更新过的点，一旦有自环，前驱节点就会发生错误,但是最后结果不会变

dij求负权边最长路和正权边最短路，求不了正权边最长路
flord求不了最长路
https://blog.csdn.net/lviiii/article/details/42365399
2:
多源最短路（弗洛伊德）:
初始话g[i][i] = 0 , 其他为正无穷 而prim 和 dij 不用0 ， 因为自环不会影响结果。
而多源最短路，边权大于0，就要更新成0 ， 因为自环会影响，如果负环，就可以加入最短路。

AOV网络：拓扑图（有向无环图）
源点汇点（可能有多个源点），每条边都有大于等于0的权值
简称：最长路 事件是点，活动是边 dp求 f[i] = f[前驱] + 边
事件最早开始时间：
事件最迟开始时间：
活动。。。。。。：
活动。。。。。。：
关键活动，关键事件（最早，最晚相等）

邻接矩阵 g[i][j] g^m次幂 表示 从i走到j ， 走m步的方案数。
假设m=2 f[i][j][2] = 西格玛f[i][k][1] * g[k][j];