数据结构课件：最短路径.pptx

最短路径

本讲要点什么问题可以抽象为求最短路径？单源最短路径算法多源最短路径算法（每对顶点之间的最短路径）

导学案例2：设计简单的旅游交通费用查询软件某城市中n个旅游景点间有旅游交通线相连，所花费的代价不尽相同。请设计一个简单的旅游线路查询系统，便于游客查询从任一个景点到另一个景点之间的最低交通花费。对于一个不带权图，两个连通顶点间经过的边或弧的数量称为路径长度；对于一个带权图，两个连通顶点间经过的所有边或弧上的权值之和称为路径长度。由于图中从一个顶点（源点）到另一个顶点（终点）可能存在多条不同的路径，各条路径的长度也不尽相同，其中路径长度最短的那条称为最短路径。求图中某顶点到其余各顶点的最短路径问题，也称为单源最短路径问题；另一类是求图中每对顶点之间的最短路径问题。

1.单源最短路径算法——Dijkstra算法问题描述：给定带权有向图G＝(V,E)和源点v∈V，求从v到G中其余各顶点的最短路径。迪杰斯特拉（Dijkstra）提出了一个按路径长度递增的次序产生最短路径的算法——Dijkstra算法。

1.单源最短路径算法——Dijkstra算法10432105030101002060S={0}0→1:(0,1)100→2:(0,2)∞0→3:(0,3)300→4:(0,4)100

1.单源最短路径算法——Dijkstra算法0432105030101002060S={0,1}0→1:(0,1)100→2:(0,1,2)600→3:(0,3)300→4:(0,4)1001

1.单源最短路径算法——Dijkstra算法042105030101002060S={0,1,3}0→1:(0,1)100→2:(0,3,2)500→3:(0,3)300→4:(0,3,4)9031

1.单源最短路径算法——Dijkstra算法04105030101002060S={0,1,3,2}0→1:(0,1)100→2:(0,3,2)500→3:(0,3)300→4:(0,3,2,4)60321

1.单源最短路径算法——Dijkstra算法0105030101002060S={0,1,3,2,4}0→1:(0,1)100→2:(0,3,2)500→3:(0,3)300→4:(0,3,2,4)601324

1.单源最短路径算法——Dijkstra算法算法的关键？图的存储结构：带权的邻接矩阵存储结构数组dist[n]：每个分量dist[i]表示当前所找到的从源点v到终点vi的最短路径的长度。初态为：若从v到vi有弧，则dist[i]为弧上权值；否则置dist[i]为∞。数组path[n]：path[i]保存了从源点v到终点vi的最短路径上该顶点的前驱顶点的序号。数组s[n]：记录已求出最短路径的顶点集合。

2.多源最短路径算法——Floyd算法问题描述：给定带权有向图G＝(V,E)，对任意顶点vi,vj∈V（i≠j），求顶点vi到顶点vj的最短路径方法1：每次以一个顶点为源点，调用Dijkstra算法n次。显然，时间复杂度为O(n3)。方法2：弗洛伊德提出的求每一对顶点之间的最短路径算法——Floyd算法，其时间复杂度也是O(n3)，但形式上要简单些。

2.多源最短路径算法——Floyd算法04116023∞0有向网图邻接矩阵021346112

2.多源最短路径算法——Floyd算法dist-1=04116023∞0path-1=0102101220初始化021346112

2.多源最短路径算法——Floyd算法dist-1=04116023∞0path-1=0102101220第1次迭代dist0=0411602370path0=0102101220201021346112

2.多源最短路径算法——Floyd算法第2次迭代dist0=0411602370path0=0102101220201dist1=0