8.6单源最短路径.ppt
- 文档编号:18817889
- 上传时间:2023-12-11
- 格式:PPT
- 页数:22
- 大小:1.56MB
8.6单源最短路径.ppt
《8.6单源最短路径.ppt》由会员分享,可在线阅读,更多相关《8.6单源最短路径.ppt(22页珍藏版)》请在冰点文库上搜索。
8.6单源最短路径,生活中常见的“最短路径”问题,单源最短路径问题,算法思想,算法分析,Dijkstra算法设计与实现,数据结构及组织,课堂练习,单源最短路径:
给定有向图G和源点v,求v到G中其余各顶点的最短路径。
相关概念,路径长度:
一条路径上所经过的边的数目,带权路径长度:
路径上所经过边的权值之和,最短路径:
(带权)路径长度(值)最小的那条路径最短路径长度或最短距离:
其(带权)路径长度,(a)有向带权图;(b)邻接矩阵,单源最短路径基本概念,单源最短路径-算法思想,距离源点最近的一个结点是?
源,有n个结点的网络,单源最短路径-算法思想,距离源点最近的一个结点是?
第二近的是?
源,有n个结点的网络,单源最短路径-算法思想,距离源点最近的一个结点是?
第二近的是?
第三近的会出现在那些路径上?
源,有n个结点的网络,单源最短路径-算法思想,距离源点最近的一个结点是?
第二近的是?
第三近的会出现在那些路径上?
路径冲突怎么办?
源,有n个结点的网络,单源最短路径-算法思想,接下去,距离源点第4、第5.第n近的结点?
源,Dijkstra求解单源最短路径思想:
按从某顶点到其它顶点的路径长度递增的方式,逐渐求到各顶点的最短路径。
有n个结点的网络,设给定源点为Vs,S为已求得最短路径的终点集,开始时令S=Vs。
当求得第一条最短路径(Vs,Vi)后,S为Vs,Vi。
根据以下结论可求下一条最短路径。
设下一条最短路径终点为Vj,则Vj只有:
源点到终点有直接的弧;从Vs出发到Vj的这条最短路径所经过的所有中间顶点必定在S中。
即只有这条最短路径的最后一条弧才是从S内某个顶点连接到S外的顶点Vj。
若定义一个数组distn,其每个disti分量保存从Vs出发中间只经过集合S中的顶点而到达Vi的所有路径中长度最小的路径长度值,则下一条最短路径的终点Vj必定是不在S中且值最小的顶点,即:
disti=Mindistk|VkV-S利用上述公式就可以依次找出下一条最短路径。
单源最短路径-算法思想,源,Dijkstra单源最短路径算法-数据组织,源,有n个结点的网络,数据源已确定结点集S待选结点集V-S结点临时最短路径长度结点临时最短路径,单源最短路径运算过程表,邻接矩阵,图,数据源邻接矩阵已确定结点集S待选结点集V-S结点临时最短路径长度Distance数组结点临时最短路径Path数组,Dijkstra算法-数据组织,单源最短路径运算过程表,Dijkstra算法例子,邻接矩阵,图,例:
计算从A点出发的单源最短路径,单源最短路径运算过程表,Dijkstra算法例子,邻接矩阵,图,例:
计算从A点出发的单源最短路径,单源最短路径运算过程表,Dijkstra算法例子,邻接矩阵,图,例:
计算从A点出发的单源最短路径,单源最短路径运算过程表,Dijkstra算法例子,邻接矩阵,图,例:
计算从A点出发的单源最短路径,单源最短路径运算过程表,Dijkstra算法例子,邻接矩阵,图,例:
计算从A点出发的单源最短路径,单源最短路径运算结果,Dijkstra算法例子,邻接矩阵,图,通过Distance数组得到最短路径长度:
D:
22通过对Path数组的反向搜索得到最短路径,如D结点相对于源点A的最短路径:
DFCA,例:
计算从A点出发的单源最短路径,Dijkstra算法步骤,令S=Vs,用带权的邻接矩阵表示有向图,对图中每个顶点Vi按以下原则置初值:
选择一个顶点Vj,使得:
Distancej=MinDistancek|VkV-SVj就是求得的下一条最短路径终点,将Vj并入到S中,即S=SVj。
对V-S中的每个顶点Vk,修改distk,方法是:
若Distancej+WjkDistancek,则修改为:
Distancek=Distancej+Wjk(VkV-S)重复,直到S=V为止。
Dijkstra算法实现,参数:
输入:
带权图G;源点序号v0;输出:
distance用来存放得到的从源点v0到其余各顶点的最短距离数值;path用来存放得到的从源点v0到其余各顶点的最短路径上到达目标顶点的前一顶点下标。
Dijkstra函数设计:
voidDijkstra(AdjMWGraph&G,intv0,intdistance,intpath)/带权图G从下标v0顶点到其他顶点的最短距离distance/和相应的目标顶点的前一顶点下标path/见教材P275页,Dijkstra算法的主要执行是:
数组变量的初始化:
时间复杂度是O(n);求最短路径的二重循环:
时间复杂度是O(n2);因此,整个算法的时间复杂度是O(n2)。
Dijkstra算法算法分析,单源最短路径运算过程表,邻接矩阵,图,计算从C点出发的单源最短路径,完成下列单源最短路径计算表格。
课堂练习,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 8.6 单源最短 路径
![提示](https://static.bingdoc.com/images/bang_tan.gif)