数据结构最短路径课件

数据结构最短路径v2V1v4v3132145数据结构最短路径v2V1v4v31321452我想去俱乐部看演出。一、问题描述综合楼校大门俱乐部图书馆2我想去俱乐部看演出。一、问题描述综合楼校大门俱乐部图书馆3我该怎么走呢？一、问题描述综合楼校大门俱乐部图书馆线路一：校大门3我该怎么一、问题描述综合楼校大门俱乐部图书馆线路一：校大门4我该怎么走呢？一、问题描述综合楼校大门俱乐部图书馆线路一：校大门俱乐部4我该怎么一、问题描述综合楼校大门俱乐部图书馆线路一：校大门5我该怎么走呢？一、问题描述综合楼校大门俱乐部图书馆线路一：校大门俱乐部线路二：校大门5我该怎么一、问题描述综合楼校大门俱乐部图书馆线路一：校大门我该怎么走呢？6综合楼校大门俱乐部图书馆一、问题描述线路二：校大门信息学院线路一：校大门俱乐部我该怎么6综合楼校大门俱乐部图书馆一、问题描述线路二：校大门7综合楼校大门俱乐部图书馆一、问题描述线路二：校大门信息学院图书馆我该怎么走呢？线路一：校大门俱乐部7综合楼校大门俱乐部图书馆一、问题描述线路二：校大门信息学院8综合楼校大门俱乐部图书馆一、问题描述线路二：校大门信息学院图书馆我该怎么走呢？线路一：校大门俱乐部俱乐部8综合楼校大门俱乐部图书馆一、问题描述线路二：校大门信息学院9综合楼校大门俱乐部图书馆一、问题描述线路二：校大门信息学院线路一：校大门俱乐部图书馆俱乐部哪条线路最短呢？9综合楼校大门俱乐部图书馆一、问题描述线路二：校大门信息学院10综合楼俱乐部图书馆一、问题描述v010综合楼俱乐部图书馆一、问题描述v011俱乐部图书馆一、问题描述v0v111俱乐部图书馆一、问题描述v0v112俱乐部v2一、问题描述v0v112俱乐部v2一、问题描述v0v113俱乐部v2一、问题描述v0v1v313俱乐部v2一、问题描述v0v1v314v4v2一、问题描述v0v1v314v4v2一、问题描述v0v1v315

由顶点集

和边集所描述的数据结构

记作G＝(V，E)其中，V为图中顶点的非空有限集合

E为图中有向边的有限集合G=（V，E）V={v0,v1,v4}E={<v0,v1>,<v0,v4>}二、图的定义与术语v1v0v4GG1、图：15由顶点集和边集所描述的数据16二、图的定义与术语v1v0v4v3v22、路径：一个顶点到另一个顶点所经历的顶点序列16二、图的定义与术语v1v0v4v3v22、路径：一个顶点17二、图的定义与术语v1v0v4v3v22、路径：一个顶点到另一个顶点所经历的顶点序列17二、图的定义与术语v1v0v4v3v22、路径：一个顶点18二、图的定义与术语v1v0v4v3v22、路径：一个顶点到另一个顶点所经历的顶点序列18二、图的定义与术语v1v0v4v3v22、路径：一个顶点19二、图的定义与术语v1v0v4v3v22、路径：一个顶点到另一个顶点所经历的顶点序列19二、图的定义与术语v1v0v4v3v22、路径：一个顶点20二、图的定义与术语v1v0v4v3v22、路径：一个顶点到另一个顶点所经历的顶点序列20二、图的定义与术语v1v0v4v3v22、路径：一个顶点21二、图的定义与术语v1v0v4v3v22、路径：一个顶点到另一个顶点所经历的顶点序列21二、图的定义与术语v1v0v4v3v22、路径：一个顶点22二、图的定义与术语v1v0v4v3v22、路径：一个顶点到另一个顶点所经历的顶点序列22二、图的定义与术语v1v0v4v3v22、路径：一个顶点23二、图的定义与术语v1v0v4v3v22、路径：一个顶点到另一个顶点所经历的顶点序列23二、图的定义与术语v1v0v4v3v22、路径：一个顶点24二、图的定义与术语v1v0v4v3v23、权值：各有向边所对应的代价2、路径：一个顶点到另一个顶点所经历的顶点序列24二、图的定义与术语v1v0v4v3v23、权值：各有向254、最短路径：两点之间权值之和最小的路径二、图的定义与术语v1v0v4v3v21003060101020503、权值：一个顶点到另一个顶点所经历的顶点序列各有向边所对应的代价2、路径：254、最短路径：两点之间权值之和最小的路径二、图的定义与术26v1v0v4v3v2100306010102050如何求从v0到v4的最短路径？26v1v0v4v3v2100306010102050如何求27路径一：v0v4路径二：路径三：路径四：v0v3v4v0v1v2v4v0v3v2v4v1v0v4v3v2100306010102050如何求从v0到v4的最短路径？27路径一：v0v4路径二：路径三：路径四：v0v3v4v028路径一：v0v4路径二：路径三：路径四：v0v3v4v0v1v2v4v0v3v2v4如何求从v0到v4的最短路径？v1v0v4v3v2100306010102050直接到达28路径一：v0v4路径二：路径三：路径四：v0v3v4v029路径一：v0v4路径二：路径三：路径四：v0v3v4v0v1v2v4v0v3v2v4如何求从v0到v4的最短路径？间接到达直接到达v1v0v4v3v210030601010205029路径一：v0v4路径二：路径三：路径四：v0v3v4v030v1v0v4v3v2100306010102050如何求从源点v0到其余各顶点的最短路径？30v1v0v4v3v2100306010102050如何求②下一条最短路径？31三、Dijkstra算法Dijkstra，荷兰人。曾在1972年获得过图灵奖。最短路径算法(SPF)和银行家算法的创造者1.

基本思想①权值之和最小的最短路径？只含一条有向边，且权值最小③其余最短路径？直接从源点到该点；从源点经过已求得最短路径的顶点，再到达该顶点。直接从源点到该点从源点经过顶点vi，再到达该顶点(由两条有向边组成)。

按各路径权值之和由小到大的顺序，产生从源点到其余各顶点的最短路径。②下一条最短路径？31三、Dijkstra算法Dijkstr322.

算法描述①计算从源点直接到达各顶点的权值；③借助步骤②中得到的顶点，计算从源点间接到达各顶点的权值之和，如小于①中权值之和，则替换；②选择权值最小的路径；④重复步骤②③，直到找到从源点到其余各顶点的最短路径。三、Dijkstra算法322.算法描述①计算从源点直接到达各顶点的权值；③借助步33v1v2v3v4S顶点从V0到各点的最短路径及其长度10(v0,v1)30(v0,v3)(v0,v4)100{v0}3.具体实现：v1v0v4v3v2100306010102050i=1∞33v1v2v3v4S顶点34v1v2v3v4S10(v0,v1)30(v0,v3)(v0,v4)100i=1顶点从V0到各点的最短路径及其长度3.具体实现：v1v0v4v3v2100306010102050{v0,v1}∞34v1v2v3v4S10(v35v1v2v3v4S10(v0,v1)30(v0,v3)(v0,v4)100{v0,v1}6030(v0,v3)(v0,v4)100i=1i=2顶点从V0到各点的最短路径及其长度3.具体实现：v1v0v4v3v2100306010102050(v0,v1,v2)∞35v1v2v3v4S10(v36v1v2v3v4S10(v0,v1)∞30(v0,v3)(v0,v4)100{v0,v1}6030(v0,v3)(v0,v4)100{v0,v1,v3}i=1i=2顶点从V0到各点的最短路径及其长度3.具体实现：v1v0v4v3v2100306010102050(v0,v1,v2)36v1v2v3v4S10(v37v1v2v3v4S10(v0,v1)∞30(v0,v3)(v0,v4)100{v0,v1}60(v0,v1,v2)30(v0,v3)(v0,v4)100{v0,v1,v3}50(v0,v3,v2)(v0,v3,v4)90i=1i=2i=3顶点从V0到各点的最短路径及其长度3.具体实现：v1v0v4v3v210030601010205037v1v2v3v4S10(v38v1v2v3v4S10(v0,v1)∞30(v0,v3)(v0,v4)100{v0,v1}{v0,v1,v3,v2}60(v0,v1,v2)30(v0,v3)(v0,v4)100{v0,v1,v3}50(v0,v3,v2)(v0,v3,v4)9060(v0,v3,v2,v4)i=1i=2i=3i=4顶点从V0到各点的最短路径及其长度3.具体实现：v1v0v4v3v210030601010205038v1v2v3v4S10(v39v1v2v3v4S10(v0,v1)∞30(v0,v3)(v0,v4)100{v0,v1}{v0,v1,v3,v2}60(v0,v1,v2)30(v0,v3)(v0,v4)100{v0,v1,v3}50(v0,v3,v2)(v0,v3,v4)9060(v0,v3,v2,v4){v0,v1,v3,v2,v4}i=1i=2i=3i=4顶点从V0到各点的最短路径及其长度3.具体实现：v1v0v4v3v210030601010205039v1v2v3v4S10(v40经开区要建一个消防站，如图所示，其中各顶点表示开发区中5个消防重点单位，分析消防站选址问题思考：v1v0v4v3v210030601010205040经开区要建一个消防站，如图所示，其中各顶点表示开发区中541Thanks!41Thanks!数据结构最短路径v2V1v4v3132145数据结构最短路径v2V1v4v313214543我想去俱乐部看演出。一、问题描述综合楼校大门俱乐部图书馆2我想去俱乐部看演出。一、问题描述综合楼校大门俱乐部图书馆44我该怎么走呢？一、问题描述综合楼校大门俱乐部图书馆线路一：校大门3我该怎么一、问题描述综合楼校大门俱乐部图书馆线路一：校大门45我该怎么走呢？一、问题描述综合楼校大门俱乐部图书馆线路一：校大门俱乐部4我该怎么一、问题描述综合楼校大门俱乐部图书馆线路一：校大门46我该怎么走呢？一、问题描述综合楼校大门俱乐部图书馆线路一：校大门俱乐部线路二：校大门5我该怎么一、问题描述综合楼校大门俱乐部图书馆线路一：校大门我该怎么走呢？47综合楼校大门俱乐部图书馆一、问题描述线路二：校大门信息学院线路一：校大门俱乐部我该怎么6综合楼校大门俱乐部图书馆一、问题描述线路二：校大门48综合楼校大门俱乐部图书馆一、问题描述线路二：校大门信息学院图书馆我该怎么走呢？线路一：校大门俱乐部7综合楼校大门俱乐部图书馆一、问题描述线路二：校大门信息学院49综合楼校大门俱乐部图书馆一、问题描述线路二：校大门信息学院图书馆我该怎么走呢？线路一：校大门俱乐部俱乐部8综合楼校大门俱乐部图书馆一、问题描述线路二：校大门信息学院50综合楼校大门俱乐部图书馆一、问题描述线路二：校大门信息学院线路一：校大门俱乐部图书馆俱乐部哪条线路最短呢？9综合楼校大门俱乐部图书馆一、问题描述线路二：校大门信息学院51综合楼俱乐部图书馆一、问题描述v010综合楼俱乐部图书馆一、问题描述v052俱乐部图书馆一、问题描述v0v111俱乐部图书馆一、问题描述v0v153俱乐部v2一、问题描述v0v112俱乐部v2一、问题描述v0v154俱乐部v2一、问题描述v0v1v313俱乐部v2一、问题描述v0v1v355v4v2一、问题描述v0v1v314v4v2一、问题描述v0v1v356

由顶点集

和边集所描述的数据结构

记作G＝(V，E)其中，V为图中顶点的非空有限集合

E为图中有向边的有限集合G=（V，E）V={v0,v1,v4}E={<v0,v1>,<v0,v4>}二、图的定义与术语v1v0v4GG1、图：15由顶点集和边集所描述的数据57二、图的定义与术语v1v0v4v3v22、路径：一个顶点到另一个顶点所经历的顶点序列16二、图的定义与术语v1v0v4v3v22、路径：一个顶点58二、图的定义与术语v1v0v4v3v22、路径：一个顶点到另一个顶点所经历的顶点序列17二、图的定义与术语v1v0v4v3v22、路径：一个顶点59二、图的定义与术语v1v0v4v3v22、路径：一个顶点到另一个顶点所经历的顶点序列18二、图的定义与术语v1v0v4v3v22、路径：一个顶点60二、图的定义与术语v1v0v4v3v22、路径：一个顶点到另一个顶点所经历的顶点序列19二、图的定义与术语v1v0v4v3v22、路径：一个顶点61二、图的定义与术语v1v0v4v3v22、路径：一个顶点到另一个顶点所经历的顶点序列20二、图的定义与术语v1v0v4v3v22、路径：一个顶点62二、图的定义与术语v1v0v4v3v22、路径：一个顶点到另一个顶点所经历的顶点序列21二、图的定义与术语v1v0v4v3v22、路径：一个顶点63二、图的定义与术语v1v0v4v3v22、路径：一个顶点到另一个顶点所经历的顶点序列22二、图的定义与术语v1v0v4v3v22、路径：一个顶点64二、图的定义与术语v1v0v4v3v22、路径：一个顶点到另一个顶点所经历的顶点序列23二、图的定义与术语v1v0v4v3v22、路径：一个顶点65二、图的定义与术语v1v0v4v3v23、权值：各有向边所对应的代价2、路径：一个顶点到另一个顶点所经历的顶点序列24二、图的定义与术语v1v0v4v3v23、权值：各有向664、最短路径：两点之间权值之和最小的路径二、图的定义与术语v1v0v4v3v21003060101020503、权值：一个顶点到另一个顶点所经历的顶点序列各有向边所对应的代价2、路径：254、最短路径：两点之间权值之和最小的路径二、图的定义与术67v1v0v4v3v2100306010102050如何求从v0到v4的最短路径？26v1v0v4v3v2100306010102050如何求68路径一：v0v4路径二：路径三：路径四：v0v3v4v0v1v2v4v0v3v2v4v1v0v4v3v2100306010102050如何求从v0到v4的最短路径？27路径一：v0v4路径二：路径三：路径四：v0v3v4v069路径一：v0v4路径二：路径三：路径四：v0v3v4v0v1v2v4v0v3v2v4如何求从v0到v4的最短路径？v1v0v4v3v2100306010102050直接到达28路径一：v0v4路径二：路径三：路径四：v0v3v4v070路径一：v0v4路径二：路径三：路径四：v0v3v4v0v1v2v4v0v3v2v4如何求从v0到v4的最短路径？间接到达直接到达v1v0v4v3v210030601010205029路径一：v0v4路径二：路径三：路径四：v0v3v4v071v1v0v4v3v2100306010102050如何求从源点v0到其余各顶点的最短路径？30v1v0v4v3v2100306010102050如何求②下一条最短路径？72三、Dijkstra算法Dijkstra，荷兰人。曾在1972年获得过图灵奖。最短路径算法(SPF)和银行家算法的创造者1.

基本思想①权值之和最小的最短路径？只含一条有向边，且权值最小③其余最短路径？直接从源点到该点；从源点经过已求得最短路径的顶点，再到达该顶点。直接从源点到该点从源点经过顶点vi，再到达该顶点(由两条有向边组成)。

按各路径权值之和由小到大的顺序，产生从源点到其余各顶点的最短路径。②下一条最短路径？31三、Dijkstra算法Dijkstr732.

算法描述①计算从源点直接到达各顶点的权值；③借助步骤②中得到的顶点，计算从源点间接到达各顶点的权值之和，如小于①中权值之和，则替换；②选择权值最小的路径；④重复步骤②③，直到找到从源点到其余各顶点的最短路径。三、Dijkstra算法322.算法描述①计算从源点直接到达各顶点的权值；③借助步74v1v2v3v4S顶点从V0到各点的最短路径及其长度10(v0,v1)30(v0,v3)(v0,v4)100{v0}3.具体实现：v1v0v4v3v2100306010102050i=1∞33v1v2v3v4S顶点75v1v2v3v4S10(v0,v1)30(v0,v3)(v0,v4)100i=1顶点从V0到各点的最短路径及其长度3.具体实现：v1v0v4v3v2100306010102050{v0,v1}∞34v1v2v3v4S10(v76v1v2v3v4S10(v0,v1)30(v0,v3)(v0,v4)100{v0,v1}6030(v0,v3)(v0,v4)100i=1i=2顶点从V0到各点的最短路径及其长度3.具体实现：v1v0v4v3v2100306010102050(v0,v1,v2)∞35v1v2v3v4S10(v77v1v2v3v4S10(v0,v1)∞30(v0,v3)(v0,v4)100{v0,v1}6030(v0,v3)(v0,v4)100{v0,v1,v3}i=1i=2顶点从V0到各点的最短路径及其长度3.具体实现：v1v0v4v3v2100306010102050(v0,v1,v2)36v1v2v3v4S10(v78v1v2v3v4S10(v0,v1)∞30(v0,v3)(v0,v4)100{v0,v1}60(v0,v1,v2)30(v0,v3)(v0,v4)100{v0,v1,v3}50