图论_dijkstra.ppt
《图论_dijkstra.ppt》由会员分享,可在线阅读,更多相关《图论_dijkstra.ppt(13页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、 赋权图的最短路算法赋权图的最短路算法 dijkstra算法算法在图的点或者边上表明某种信息的数,称为权,含有权的图称为赋权图。下图就是在图的点或者边上表明某种信息的数,称为权,含有权的图称为赋权图。下图就是一个公路网络交通图。一个公路网络交通图。如果从如果从a点出发,那么如何寻找一条点出发,那么如何寻找一条从点从点a到其他各点的通路,使得通路到其他各点的通路,使得通路上各边的权和最小。接下来介绍著名上各边的权和最小。接下来介绍著名的迪克斯特拉算法。这个算法很著名,的迪克斯特拉算法。这个算法很著名,应用很广泛,比如路由器搜寻节点采应用很广泛,比如路由器搜寻节点采用的就是由该算法改进而来。用的就
2、是由该算法改进而来。Dijkstra算法是解单源最短路径的一个贪心算法。其本思想是。设置一个顶点算法是解单源最短路径的一个贪心算法。其本思想是。设置一个顶点集合,并不断的作贪心选择来扩充这个集合。一个顶点属于集合,并不断的作贪心选择来扩充这个集合。一个顶点属于S当且仅当从源到当且仅当从源到该顶点的最短路径及其长度已知。初始时,该顶点的最短路径及其长度已知。初始时,S中仅有源。假设中仅有源。假设u是是G(V,E)的)的某一个顶点,我们把从源到某一个顶点,我们把从源到u且中间只经过且中间只经过S中顶点的路称为从源到中顶点的路称为从源到u的特殊的特殊路径(当前最短路径),用路径(当前最短路径),用d
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 图论 _dijkstra
限制150内