图论的一些算法总结

一、最短路径

1、Dijkstra:单源最短路径算法

每加入一个点,都跟新到源点的最短路径(相比较而言prim算法则跟新到所有已经加入的点的最短路径)

不能存在负边,因为每加入一个点,那么源到这个点的最小值就确定下来了

反证法:图论的一些算法总结

 

2、floyd:任意两点之间的最短路径

3、bellman-ford:允许负边但不允许负环

每次加入一条边都有可能修改最短路径值

4、spfa :经过队列优化的bellman-ford算法

二、最小生成树

1、kruscal:选边

2、prim:选点

 

上一篇:最小生成树-prim


下一篇:【Ybtoj 第11章例2】新的开始【最小生成树】