//看一下bellman_ford:其实他就是通过不断的松弛构造一颗以源点为根的最短路径树,原算法中第i次松弛结束后一定能生成从树根到结点长度不超过i的最短距的点中的最短距离(说的好绕哟) //注意,没优化的bellman并不保证松弛i次后每一个距离都是路径长度为i的最短的,因为它松弛边的时候无序,可能得到>i次的松弛结果 //所以使用spfa标记点的距离,,还有需要注意的是我们要开二维数组标记,,因为显然我们无法确定一个更短权 和 一个更短路 对它所邻接点更新时谁会使得最终结果更优 #include <…

2011年4月21日 0条评论 0点热度 阅读全文