图的最短路径_dijkstra算法

图的最短路径_dijkstra算法

ID:45943425

大小:690.00 KB

页数:29页

时间:2019-11-19

图的最短路径_dijkstra算法_第1页
图的最短路径_dijkstra算法_第2页
图的最短路径_dijkstra算法_第3页
图的最短路径_dijkstra算法_第4页
图的最短路径_dijkstra算法_第5页
资源描述:

《图的最短路径_dijkstra算法》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库

1、1基本图算法陈嘉庆最短路径问题单源最短路径Single-SourceShortestPath问题:带权有向图G(E,V),找出从给定源顶点s到其它顶点v的权最小路径。“最短路径”=最小权路径的权是路径上所有边的权之和。例:道路图:从华师中山附中到市政府的最短路径?若顶点序列{V0,V1,…,Vn}是从V0到Vn的最短路,则序列{V0,V1,…,Vn-1}必为从V0到Vn-1的最短路。贪心算法权非负的单源最短路径算法(Dijkstra)12345612653723892v5v4v01005601010v1v2v3205030图中从v0到其余各顶点之间的最短

2、路径:v0到v1无v0到v2(v0,v2)10v0到v3(v0,v4,v3)50v0到v4(v0,v4)30v0到v5(v0,v4,v3,v5)60单源最短路径基本思想:将图中所有顶点分成两组:S,V-S一组是包括已确定最短路径的顶点的集合S,另一组是尚未确定的最短路径的顶点集V-S。S初始仅包含源v0,不断在V-S做贪心选择扩充集合S。权非负的单源最短路径算法(Dijkstra)权非负的单源最短路径算法(Dijkstra)初始时,S仅包含源v0,特殊路径:从源到G中某一顶点u且中间只经过S中顶点的路称为从源到u的特殊路径。步骤:(1)取v0加入S中(2

3、)从V-S中取出具有当前最短路径长度的顶点w加入S中。最短路径——Dijkstra算法实例812345612653723892例求下图中顶点1到其余各顶点的最短路径。10123∞∞∞8510364142512(1)初始化:1到v,若有边,则path[v]=边;dist[i]=边的值(2)选出dist[i]为最小值,则path[i]为1到i的最短路径(3)修改经过i更近的路径(4)重复(2)(3)最短路径——Dijkstra算法描述方法如下:(其中:path[v]和dist[v]表示从v0到v的最短路径及其长度)(1)对v0以外的各顶点vi,若<

4、v0,vi>存在,则将其作为v0到vi的(暂时的)最短路径存放到path[v]中,将其权值作为对应的路径长度存放到dist[v]中。(2)从未解顶点中选择一个dist值最小的顶点v,则当前的path[v]和dist[v]就是顶点v的最终解。(3)由于某些顶点经过v可能会使得从v0到该顶点的路径更近一些,因此,应修改这些顶点的路径及其长度的值。(4)重复(2)(3),直到所有顶点求解完毕。9136425最短路径——Dijkstra算法实例顶点pathdist12345610实例:123456126537238920123∞∞∞()(1,2)(1,3)()(

5、)()(1,3,2)85(1,3,4)(1,3,5)10(1,3,4,6)14(1,3,5,6)12Dijkstra算法:一般情况下,Dist[k]=<源点到顶点i的弧上的权值>或者=<源点到其它顶点的路径长度>+<其它顶点到顶点i的弧上的权值>设置辅助数组Dist,其中每个分量Dist[i]表示当前所求得的从源点到其余各顶点i的最短路径的长度。1)在所有从源点出发的弧中选取一条权值最小的弧,即为第一条最短路径。2)修改其它各顶点的Dist[i]值。假设求得最短路径的顶点为u,若Dist[u]+G.arcs[u][i]

6、为Dist[u]+G.arcs[u][i]V0和i之间存在弧V0和i之间不存在弧其中的最小值即为最短路径的长度。单源最短路径Single-SourceShortestPathDijkstra的时间复杂度是O(N2),它不能处理存在负边权的情况。算法描述:设起点为s,dis[v]表示从s到v的最短路径,pre[v]为v的前驱节点,用来输出路径。a)初始化:dis[v]=∞(v≠s);dis[s]=0;pre[s]=0;b)For(i=1;i<=n;i++)1.在没有被访问过的点中找一个顶点u使得dis[u]是最小的。2.u标记为已确定最短路径3.For与u

7、相连的每个未确定最短路径的顶点vif(dis[u]+w[u][v]

8、点1到某一点V0的最短路径要经过中转点Vi,那么中转点Vi一定是先于V0被确定了

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。