最短路算法专题

2021/10/19 9:09:31

本文主要是介绍最短路算法专题,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

一、知识结构图

二、Dijkstra算法

单源最短路径

思想:广度和贪心

步骤:

  1、当到一个时间点时,图上部分的点的最短距离已确定,部分点的最短距离未确定。
  
  2、选一个所有未确定点中离源点最近的点,把他认为成最短距离。
  
  3、再把这个点所有出边遍历一边,更新所有的点。

三、Floyd算法

多源最短路径
思想:动态规划

步骤:

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.再一次遍历所有边,是不是存在有最小边的值还在变小,如果有变小就存在负环。



这篇关于最短路算法专题的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程