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)逐步试着在原直接路径中增加中间顶点,若加入中间顶点后路径变短,则修改,否则维持原值,所有顶点试探完后,算法结束。