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

1、最短路径最短路径v2V1v4v3132145数据结构数据结构 最短路径最短路径2我想去俱乐部我想去俱乐部看演出。看演出。一、问题描述一、问题描述综合楼综合楼校大门校大门俱乐部俱乐部图书馆图书馆数据结构数据结构 最短路径最短路径3我该怎么我该怎么走呢？走呢？一、问题描述一、问题描述综合楼综合楼校大门校大门俱乐部俱乐部图书馆图书馆线路一：线路一：校大门校大门数据结构数据结构 最短路径最短路径4我该怎么我该怎么走呢？走呢？一、问题描述一、问题描述综合楼综合楼校大门校大门俱乐部俱乐部图书馆图书馆线路一：线路一：校大门校大门俱乐部俱乐部数据结构数据结构 最短路径最短路径5我该怎么我该怎么走呢？走呢？一、

2、问题描述一、问题描述综合楼综合楼校大门校大门俱乐部俱乐部图书馆图书馆线路一：线路一：校大门校大门俱乐部俱乐部线路二：线路二：校大门校大门数据结构数据结构 最短路径最短路径我该怎么我该怎么走呢？走呢？6综合楼综合楼校大门校大门俱乐部俱乐部图书馆图书馆一、问题描述一、问题描述线路二：线路二：校大门校大门信息学院信息学院线路一：线路一：校大门校大门俱乐部俱乐部数据结构数据结构 最短路径最短路径7综合楼综合楼校大门校大门俱乐部俱乐部图书馆图书馆一、问题描述一、问题描述线路二：线路二：校大门校大门信息学院信息学院图书馆图书馆我该怎么我该怎么走呢？走呢？线路一：线路一：校大门校大门俱乐部俱乐部数据结构数据

3、结构 最短路径最短路径8综合楼综合楼校大门校大门俱乐部俱乐部图书馆图书馆一、问题描述一、问题描述线路二：线路二：校大门校大门信息学院信息学院图书馆图书馆我该怎么我该怎么走呢？走呢？线路一：线路一：校大门校大门俱乐部俱乐部俱乐部俱乐部数据结构数据结构 最短路径最短路径9综合楼综合楼校大门校大门俱乐部俱乐部图书馆图书馆一、问题描述一、问题描述线路二：线路二：校大门校大门信息学院信息学院线路一：线路一：校大门校大门俱乐部俱乐部图书馆图书馆俱乐部俱乐部哪条线路哪条线路最短呢？最短呢？数据结构数据结构 最短路径最短路径10综合楼综合楼俱乐部俱乐部图书馆图书馆一、问题描述一、问题描述v0数据结构数据结构

4、最短路径最短路径11俱乐部俱乐部图书馆图书馆一、问题描述一、问题描述v0v1数据结构数据结构 最短路径最短路径12俱乐部俱乐部v2一、问题描述一、问题描述v0v1数据结构数据结构 最短路径最短路径13俱乐部俱乐部v2一、问题描述一、问题描述v0v1v3数据结构数据结构 最短路径最短路径14v4v2一、问题描述一、问题描述v0v1v3数据结构数据结构 最短路径最短路径15 由由顶点集顶点集 和和边集边集所描述所描述的数据结构的数据结构 记作记作G(V，E)其中，其中，V为图中为图中顶点顶点的非空有限集合的非空有限集合 E为图中为图中有向边有向边的有限集合的有限集合 G=（V，E）V=v0,v1,

5、v4E=,二、图的定义与术语二、图的定义与术语v1v0v4G G1、图、图：数据结构数据结构 最短路径最短路径16二、图的定义与术语二、图的定义与术语v1v0v4v3v22、路径：、路径：一个顶点到另一个顶点所经历的一个顶点到另一个顶点所经历的顶点序列顶点序列数据结构数据结构 最短路径最短路径17二、图的定义与术语二、图的定义与术语v1v0v4v3v22、路径：、路径：一个顶点到另一个顶点所经历的一个顶点到另一个顶点所经历的顶点序列顶点序列数据结构数据结构 最短路径最短路径18二、图的定义与术语二、图的定义与术语v1v0v4v3v22、路径：、路径：一个顶点到另一个顶点所经历的一个顶点到另一个

6、顶点所经历的顶点序列顶点序列数据结构数据结构 最短路径最短路径19二、图的定义与术语二、图的定义与术语v1v0v4v3v22、路径：、路径：一个顶点到另一个顶点所经历的一个顶点到另一个顶点所经历的顶点序列顶点序列数据结构数据结构 最短路径最短路径20二、图的定义与术语二、图的定义与术语v1v0v4v3v22、路径：、路径：一个顶点到另一个顶点所经历的一个顶点到另一个顶点所经历的顶点序列顶点序列数据结构数据结构 最短路径最短路径21二、图的定义与术语二、图的定义与术语v1v0v4v3v22、路径：、路径：一个顶点到另一个顶点所经历的一个顶点到另一个顶点所经历的顶点序列顶点序列数据结构数据结构 最

7、短路径最短路径22二、图的定义与术语二、图的定义与术语v1v0v4v3v22、路径：、路径：一个顶点到另一个顶点所经历的一个顶点到另一个顶点所经历的顶点序列顶点序列数据结构数据结构 最短路径最短路径23二、图的定义与术语二、图的定义与术语v1v0v4v3v22、路径：、路径：一个顶点到另一个顶点所经历的一个顶点到另一个顶点所经历的顶点序列顶点序列数据结构数据结构 最短路径最短路径24二、图的定义与术语二、图的定义与术语v1v0v4v3v23、权、权 值：值：各有向边所对应的各有向边所对应的代价代价2、路径：、路径：一个顶点到另一个顶点所经历的一个顶点到另一个顶点所经历的顶点序列顶点序列数据结构

8、数据结构 最短路径最短路径254、最短路径：两点之间权值之和最小的路径、最短路径：两点之间权值之和最小的路径二、图的定义与术语二、图的定义与术语v1v0v4v3v21003060101020503、权、权 值：值：一个顶点到另一个顶点所经历的一个顶点到另一个顶点所经历的顶点序列顶点序列各有向边所对应的各有向边所对应的代价代价2、路径：、路径：数据结构数据结构 最短路径最短路径26v1v0v4v3v2100306010102050如何求从如何求从v0到到v4的的最短路径？最短路径？数据结构数据结构 最短路径最短路径27路径一：路径一：v0v4路径二：路径二：路径三：路径三：路径四：路径四：v0v

9、3v4v0v1v2v4v0v3v2v4v1v0v4v3v2100306010102050如何求从如何求从v0到到v4的最短路径？的最短路径？数据结构数据结构 最短路径最短路径28路径一：路径一：v0v4路径二：路径二：路径三：路径三：路径四：路径四：v0v3v4v0v1v2v4v0v3v2v4如何求从如何求从v0到到v4的最短路径？的最短路径？v1v0v4v3v2100306010102050直接到达直接到达数据结构数据结构 最短路径最短路径29路径一：路径一：v0v4路径二：路径二：路径三：路径三：路径四：路径四：v0v3v4v0v1v2v4v0v3v2v4如何求从如何求从v0到到v4的最短

10、路径？的最短路径？间接到达间接到达直接到达直接到达v1v0v4v3v2100306010102050数据结构数据结构 最短路径最短路径30v1v0v4v3v2100306010102050如何求从源点如何求从源点v0到其余到其余各顶点的最短路径？各顶点的最短路径？数据结构数据结构 最短路径最短路径下一条最短路径？下一条最短路径？3131三、三、Dijkstra算法算法DijkstraDijkstra，荷兰人。曾在，荷兰人。曾在19721972年获得过图灵奖。最短年获得过图灵奖。最短路径算法路径算法(SPF)(SPF)和银行家算和银行家算法的创造者法的创造者1.基本思想基本思想权值之和最小的最短

11、路径？权值之和最小的最短路径？只含一条有向边，只含一条有向边，且权值最小且权值最小其余最短路径？其余最短路径？直接从源点到该点；直接从源点到该点；从源点经过已求得最短路径的顶点，再到达该顶点。从源点经过已求得最短路径的顶点，再到达该顶点。直接从源点到该点直接从源点到该点从源点经过顶点从源点经过顶点vi，再到达该顶点，再到达该顶点(由两条有向边组成由两条有向边组成)。按各路径权值之和由小按各路径权值之和由小到大的顺序，产生从到大的顺序，产生从源点到源点到其余各顶点其余各顶点的最短路径。的最短路径。数据结构数据结构 最短路径最短路径322.算法描述算法描述计算从源点计算从源点直接直接到达各顶点的权

12、值；到达各顶点的权值；借助步骤中得到的顶点，计算从源点借助步骤中得到的顶点，计算从源点间接间接到达到达各顶点的权值之和，如小于各顶点的权值之和，如小于 中权值之和，则替换；中权值之和，则替换；选择权值选择权值最小最小的路径；的路径；重复步骤重复步骤，直到找到从源点到其余各顶点，直到找到从源点到其余各顶点的最短路径。的最短路径。三、三、Dijkstra算法算法数据结构数据结构 最短路径最短路径33 v1 v2 v3 v4 S顶点顶点 从从V0到各点的最短路径及其长度到各点的最短路径及其长度10(v0,v1)30(v0,v3)(v0,v4)100v03.具体实现：具体实现：v1v0v4v3v210

13、0306010102050i=1数据结构数据结构 最短路径最短路径34 v1 v2 v3 v4 S10(v0,v1)30(v0,v3)(v0,v4)100i=1顶点顶点 从从V0到各点的最短路径及其长度到各点的最短路径及其长度3.具体实现：具体实现：v1v0v4v3v2100306010102050v0,v1数据结构数据结构 最短路径最短路径35 v1 v2 v3 v4 S10(v0,v1)30(v0,v3)(v0,v4)100v0,v16030(v0,v3)(v0,v4)100i=1i=2顶点顶点 从从V0到各点的最短路径及其长度到各点的最短路径及其长度3.具体实现：具体实现：v1v0v4v

14、3v2100306010102050(v0,v1,v2)数据结构数据结构 最短路径最短路径36 v1 v2 v3 v4 S10(v0,v1)30(v0,v3)(v0,v4)100v0,v16030(v0,v3)(v0,v4)100v0,v1,v3i=1i=2顶点顶点 从从V0到各点的最短路径及其长度到各点的最短路径及其长度3.具体实现：具体实现：v1v0v4v3v2100306010102050(v0,v1,v2)数据结构数据结构 最短路径最短路径37 v1 v2 v3 v4 S10(v0,v1)30(v0,v3)(v0,v4)100v0,v160(v0,v1,v2)30(v0,v3)(v0,

15、v4)100v0,v1,v350(v0,v3,v2)(v0,v3,v4)90i=1i=2i=3顶点顶点 从从V0到各点的最短路径及其长度到各点的最短路径及其长度3.具体实现：具体实现：v1v0v4v3v2100306010102050数据结构数据结构 最短路径最短路径38 v1 v2 v3 v4 S10(v0,v1)30(v0,v3)(v0,v4)100v0,v1v0,v1,v3,v260(v0,v1,v2)30(v0,v3)(v0,v4)100v0,v1,v350(v0,v3,v2)(v0,v3,v4)9060(v0,v3,v2,v4)i=1i=2i=3i=4顶点顶点 从从V0到各点的最短路

16、径及其长度到各点的最短路径及其长度3.具体实现：具体实现：v1v0v4v3v2100306010102050数据结构数据结构 最短路径最短路径39 v1 v2 v3 v4 S10(v0,v1)30(v0,v3)(v0,v4)100v0,v1v0,v1,v3,v260(v0,v1,v2)30(v0,v3)(v0,v4)100v0,v1,v350(v0,v3,v2)(v0,v3,v4)9060(v0,v3,v2,v4)v0,v1,v3,v2,v4i=1i=2i=3i=4顶点顶点 从从V0到各点的最短路径及其长度到各点的最短路径及其长度3.具体实现：具体实现：v1v0v4v3v2100306010102050数据结构数据结构 最短路径最短路径40经开区要建一个消防站，如图所示，其中各顶点表经开区要建一个消防站，如图所示，其中各顶点表示开发区中示开发区中5个消防重点单位，分析消防站选址问题个消防重点单位，分析消防站选址问题 思考：思考：v1v0v4v3v2100306010102050数据结构数据结构 最短路径最短路径41Thanks!