最小生成树:
1.Kruskal算法(同时包含并查集)
2.prim算法
最短路径问题:
1.Dijkstra(迪杰斯特拉):适用于权值为非负的图的单源最短路径。可用于计算正权图上的单源最短路(Single-Source Shortest Paths, SSSP),即从单个源点出发，到所有结点的最短路，该算法同时适用于有向图和无向图。
2.Bellman-Ford(贝尔曼-福特):适用于权值有负值的图的单源最短路径。前提条件为不含负环。既然不含环， 最短路最多进过（起点不算）n-1个结点，通过n-1轮松弛操作（relaxation）得到。
3.spfa算法(Shortest Path Faster Algorithm):适用于权值有负值，且没有负圈的图的单源最短路径。
4.Floyd算法(弗洛伊德):每对结点之间的最短路径。给出结论(点我查看原文章):
(1)当权值为非负时，用Dijkstra。
(2)当权值有负值，且没有负圈，则用SPFA，SPFA能检测负圈，但是不能输出负圈。
(3)当权值有负值，而且可能存在负圈，则用BellmanFord，能够检测并输出负圈。
(4)SPFA检测负环：当存在一个点入队大于等于V次，则有负环。