单源最短路径
思想:广度和贪心
步骤: 1、当到一个时间点时,图上部分的点的最短距离已确定,部分点的最短距离未确定。 2、选一个所有未确定点中离源点最近的点,把他认为成最短距离。 3、再把这个点所有出边遍历一边,更新所有的点。
多源最短路径
思想:动态规划
步骤: 1、用D[v][w]记录每一对顶点的最短距离。 2、依次扫描每一个点,并以其为基点再遍历所有每一对顶点D[][]的值,看看是否可用过该基点让这对顶点间的距离更小。
Spfa算法
单源最短路径
思路:动态逼近
spfa是怎么动态逼近呢,借助一下Floyd算法,那么Floyd算法是不停的借助中间节点去变小变小,那么这里也差不多但是稍微有点不一样,spfa算法变小之后,觉得这个变小的可能会引起其他的变小,那么我们又遍历这个变小的节点,这就是动态逼近,一旦变小,就走这里,慢慢的逼近最小值。
怎么实现呢,网上的代码都借助了队列辅助,就是如果某个点的值变小,就把这个点加入队列,去寻找有没有引起其他点变小,我们也叫这个队列叫维护队列。
Spfa步骤:
1.把起始节点加入队列
2.出队,找出变小的相邻节点,如果该节点不在队列,加入队列
3.重复循环2,直到队列为空
Bellmam-Ford算法:
1.初始化最小路径数组,出来起始点之外,都置为无穷大(建议用#define INF 0x3f3f3f3f),
2.分内外循环,外循环是n个点最多通过n-1次松弛就可以达到最佳效果(这也是最难理解的),内循环是对每边加入最小边数组比较,如果最小边大于加入的边额更新(跟其他算法一样),那么这样一来,算法的时间效率就是o(v*e)v是点,e是边
3.再一次遍历所有边,是不是存在有最小边的值还在变小,如果有变小就存在负环。