单源最短路 单源最短路的意思就是一个起点,算出到其他点的最短路,这里介绍三种算法,bellman-ford,spfa和dijkstra BF算法 算法思想 BF是bellman_ford的简称,算法的想法非常简单,进行|V|−1次操作,每次操作对所有的边松弛。 松弛可以形象的理解为更新值,比如有一条从u到v的边,如果u上的值加上边的长度小于v上的值,那么就更新v上的值。 为什么这样做是对的呢?我们可以回顾整个过程,第一次操作,我们一定能将起点出去的点中的某一个点更新为最小值(这个点以后不会被更新),关于这点可以用反…

2016年7月12日 0条评论 6点热度 阅读全文