一、最短路径
1、Dijkstra:单源最短路径算法
每加入一个点,都跟新到源点的最短路径(相比较而言prim算法则跟新到所有已经加入的点的最短路径)
不能存在负边,因为每加入一个点,那么源到这个点的最小值就确定下来了
反证法:
2、floyd:任意两点之间的最短路径
3、bellman-ford:允许负边但不允许负环
每次加入一条边都有可能修改最短路径值
4、spfa :经过队列优化的bellman-ford算法
二、最小生成树
1、kruscal:选边
2、prim:选点