虽然是老东西了,今天突然不明白了,记录下
BellManFord:
根据最短路径的性质,n各节点构成的最短路中,最多有n-1条边。
于是乎,考虑最坏情况,每次更新M条边,更新N-1次就一定求出一条最短路
问题:如果已经求出的最短路,中间有结点的值被更新
ans:这个无所谓的嘛,如果被更新了,最短路相应也会变的,还是小于N-1个结点恩~
SPFA:
这个算法快在哪里?
第一,不是乱更新,每条路径(假设路径独立恩恩,没有别的东西在捣乱),只需要N-1个结点入队就可以了~
第二,如果中间有节点被更新而且这个节点隐藏在队列的阴暗的角落,那么,更新两条路径的时间会减少一些~
BellManFord:
根据最短路径的性质,n各节点构成的最短路中,最多有n-1条边。
于是乎,考虑最坏情况,每次更新M条边,更新N-1次就一定求出一条最短路
问题:如果已经求出的最短路,中间有结点的值被更新
ans:这个无所谓的嘛,如果被更新了,最短路相应也会变的,还是小于N-1个结点恩~
SPFA:
这个算法快在哪里?
第一,不是乱更新,每条路径(假设路径独立恩恩,没有别的东西在捣乱),只需要N-1个结点入队就可以了~
第二,如果中间有节点被更新而且这个节点隐藏在队列的阴暗的角落,那么,更新两条路径的时间会减少一些~