Bellman Ford算法 用途 用于解决单源最短路径问题,即在给定图和起始结点的基础上,求所有其他结点到起始结点的最短路径。与Dijkstra算法不同的是,BF算法可以处理含有负边权边的图(如果图中存在负环则不适用,因为路径可以不断穿过负环来使最短路径越来越小,无法解出答案)。 算法描述 与Dijkstra算法相似,BF算法也是利用已经找到的最短路径来更新其他结点到源点的最短路径。不同的是,Dij是有针对性的,每次并入一个距离最短的新结点后,再以该点为中转站来更新其他未访问结点到源点的最短距离;而BF算法每一次…

2018年3月12日 0条评论 5点热度 阅读全文