6.7.1 最短路径

典型用途:交通网络得问题——从甲地到乙地之间是否有公路连通?在有多条通路得情况下,哪一条路最短?

交通网路用图来表示:

顶点:表示地点

弧:表示两个地点之间有路连通

弧上的权值:表示两地点之间的距离、交通费或图中所花费的时间等。

问题抽象:在有向网中A点(源点)到达B点(终点)的多条路径中,寻找一条各边权值之和最小的路径,即最短路径。

第一类问题:两点间最短路径

第二类问题:某源点到其它各点的最短路径

两种常见的最短路径问题:

(1)单源最短路径:用Dijkstra(迪杰斯特拉)算法

(2)所有顶点间的最短路径:用Floyd(弗洛伊德)算法

6.7.2 Dijkstra算法

1、初始化:先找出从源点v0到各终点vk的直达路径(v0,vk),即通过一条弧到达的路径;

2、选择:从这些路径中找出一条长度最短的路径(v0,u);

3、更新:然后对其余各条路径进行适当调整:若在图中存在弧(u,vk),且(v0,u)+ (u,vk) <
(v0,vk),则以路径(v0,u,vk)代替(v0,vk);

4、在调整后的各条路径中,再找长度最短的路径,以此类推。

按路径长度递增次序产生最短路径:

1、把V分成两组:

(1)S:已求出最短路径的顶点的集合

(2)T = V - S:尚未确定最短路径的顶点的集合

2、将T中顶点按最短路径递增的次序加入S中:

保证:

(1)从源点v0到S中各顶点的最短路径长度都不大于从v0到T中任何顶点的最短路径长度;

(2)每个顶点对应一个距离值:

        S中顶点:从v0到此顶点的最短路径长度

        T中顶点:从v0到此路径的只包括S中顶点做中间顶点的最短路径长度

算法步骤:

1、初始时令S = {v0},T = {其余顶点}

2、T中顶点对应的距离值由辅助数组D存放,D[i]的初值:若<v0,vi>存在,则为其权值,否则为∞

3、从T中选取一个其距离最小的顶点vj,加入S,对T中顶点的距离进行修改:若加进vj作中间顶点,从v0到vi的距离值比不加vj的距离短,则修改距离值,重复上述步骤,直至S
= V为止。

 

终点从v0到各终点的最短路径
i =1i = 2i = 3i = 4i = 5i = 6
v11313
v28
v3∞1313
v430303019
v5∞∞22222121
v63232202020
vjv2v1v3v4v6v5
距离81313192021
6.7.3 Floyd算法

算法思路:

* 逐个顶点试探
* 从vi到vj的所有可能存在的路径中选出一条最短的路径
求最短路径的步骤:

(1)初始时设置一个n阶方阵,令其对角线元素为0,若存在弧<vi,vj>,则对应元素为权值,否则为∞;

(2)逐步试着在原直接路径中增加中间顶点,若加入中间顶点后路径变短,则修改,否则维持原值,所有顶点试探完后,算法结束。

 

技术
今日推荐
下载桌面版
GitHub
百度网盘(提取码:draw)
Gitee
云服务器优惠
阿里云优惠券
腾讯云优惠券
华为云优惠券
站点信息
问题反馈
邮箱:[email protected]
QQ群:766591547
关注微信