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