最短路径
两种常见的最短路径问题:
一、单源最短路径–用Dijistra迪杰斯特拉)算法
二、所有顶点间的最短路径–用Floyd(弗洛伊德)算法
Dijistra算法
1、初始化:先找出从源点v0到各终点Vk的的直达路径(V0, Vk),即通过一条弧直达的路径。
2、选择:从这些路径中找出一条长度最短的路径(V0, U)。
3、更新:然后对其余各路径进行适当调整:
若在图中存在弧(U, Vk),且(V0, U) + (U, Vk) < (V0, Vk),则以路径(V0, U, Vk)代替(V0, Vk)。
在调整的各条路径中,再找到长度最短的路径,依此类推
迪杰斯特拉(Dijkstra)算法:按路径长度递增次序产生最短路径
1、把V分成两组:
(1)S:已求出最短路径的顶点的集合。
(2)T = V - S:尚未确定最短路径的顶点集合。
2、将T中顶点按最短路径递增的次序加入到S中,
保证:(1)从源点v0到S中各项点的最短路径长度都不大于从v0到T中任何顶点的最短路径长度。
(2)每个顶点对应一个距离值:
S中顶点:从v0到此顶点的最短路径长度
T中顶点:从v0到此顶点的只包括S中顶点作中间顶点的最短路径长度
**Dijkstra算法步骤:**初始时令 S = {v0}, T = {其余顶点}。
T中选取一个其距离值最小的顶点vj,加入S。对T中顶点的距离值进行修改:若加进vj作中间顶点,从v0到vi的距离值比不加vj的路径相加,则修改此距离值。
![在这里插入图片描述](https://img-blog.csdnimg.cn/20210310215142972.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjkwMTYz,size_16,color_FFFFFF,t_70)
加入v2顶点之后
![在这里插入图片描述](https://img-blog.csdnimg.cn/20210310222417753.png)
![在这里插入图片描述](https://img-blog.csdnimg.cn/20210310222438989.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjkwMTYz,size_16,color_FFFFFF,t_70)
加入顶点v1之后
!
![在这里插入图片描述](https://img-blog.csdnimg.cn/20210310223020952.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjkwMTYz,size_16,color_FFFFFF,t_70)
依此类推,直到S = V
![在这里插入图片描述](https://img-blog.csdnimg.cn/20210310223058830.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjkwMTYz,size_16,color_FFFFFF,t_70)
Floyd算法
算法思想:逐个试探,从vi到vj的所有可能存在的路径中,选出一条长度最短的路径
求最短路径步骤:初始时设置一个n阶矩阵方针,令其对角线元素为0,若存在弧<Vi, Vj>,则其对应元素为权值;否则为∞。逐步试着在原直接路径中增加中间顶点,若加入中间顶点后路径变短,则修改;否则维持原值。所有顶点试探完毕,算法结束。
![在这里插入图片描述](https://img-blog.csdnimg.cn/20210311102649949.png)
![在这里插入图片描述](https://img-blog.csdnimg.cn/20210311102726832.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjkwMTYz,size_16,color_FFFFFF,t_70)