有向图中任意令两点之间的最短路径

有向图中任意令两点之间的最短路径

ID:14442128

大小:80.00 KB

页数:10页

时间:2018-07-28

有向图中任意令两点之间的最短路径_第1页
有向图中任意令两点之间的最短路径_第2页
有向图中任意令两点之间的最短路径_第3页
有向图中任意令两点之间的最短路径_第4页
有向图中任意令两点之间的最短路径_第5页
资源描述:

《有向图中任意令两点之间的最短路径》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库

1、有向图中任意两点之间的最短路径一.问题求出有向图中任意两点之间的最短路径并打印结果二.语言环境C++三.问题分析要解决有向图中任意两点之间的最短路径问题首先应解决的问题是1.从源点到其余各点的最短路径问题2.每一对定点之间的最短路径问题对于”从源点到其余各点的最短路径问题”有经典算法-------“迪杰斯特拉算法”.该算法的思想是:(1).如图(A)132113长度最短路径81920164320图

2、(A)路径长度最短的最短路径的特点:在这条路径上,必定只含一条弧,并且这条弧的权值最小。下一条路径长度次短的最短路径的特点:它只可能有两种情况:或者是直接从源点到该点(只含一条弧);或者是从源点经过顶点v1,再到达该顶点(由两条弧组成)。再下一条路径长度次短的最短路径的特点:它可能有三种情况:或者是直接从源点到该点(只含一条弧);或者是从源点经过顶点v1,再到达该顶点(由两条弧组成);或者是从源点经过顶点v2,再到达该顶点。其余最短路径的特点:它或者是直接从源点到该点(只含一条弧);或者是从源点经过已求得最短路径的顶点,

3、再到达该顶点。由以上特点可知:假设S为已求得最短路径的终点的集合,则可证明:下一条最短路径(设其终点为x)或者是弧(v,x),或者是中间只经过S中的顶点而最后到达终点x的路径。假设此路径上有一个顶点不在S中,则说明存在一条终点不在S中,而长度比此路径短的路径。但这是不可能的,因为我们是按路径长度递增的次序来产生最短路径的,故长度比此路径短的所有路径均已产生,他们的终点必定在S中,即假设不成立。设置辅助数组Dist,其中每个分量Dist[k]表示当前所求得的从源点到其余各顶点k的最短路径。一般情况下,Dist[k]=<源点

4、到顶点k的弧上的权值>或者=<源点到S中某顶点j的路径长度>+<顶点j到顶点k的弧上的权值>。(1). 在所有从原点出发的弧中选取一条权值最小的弧即为第一条最短路径(如图(a))V0和k之间存在弧 V0和k之间不存在弧其中的最小值即为最短路径的长度。(2). 修改其它各顶点的Dist[k]值。假设求得最短路径的顶点为u,若Dist[u]+G.arcs[u][k]

5、h[],intdist[])//path[v]为从v0到v的最短路径的前驱顶点,//dist[v]为其当前的最短距离.s为全局变量,s[v]=1,//表示v已在S集合中,即已求得从v0到v的最短距离。{For(v=0;v

6、num;++i){min=infinity;for(w=0;w

7、∞∞∞50∞∞∞∞∞∞∞10∞∞∞20∞60∞∞∞∞∞∞步骤第一步第二步第三步第四步第五步v1∞∞∞∞∞无v210(v0,v2)v3∞60(v0,v2,v3)50(v0,v4,v3)v430(v0,v4)30(v0,v4)v5100(v0,v5)100(v0,v5)90(v0,v4,v5)60(v0,v4,v3,v5)vjv2v4v3v5S{v0,v2}{v0,v2,v4}{v0,v2,v4,v3}{v0,v2,v4,v3,v5}对于”每一对定点之间的最短路径问题”有经典算法――弗洛伊德算法从vi到vj的所有可能存在的路

8、径中,选出一条长度最短的路径。若存在,则存在路径{vi,vj}//路径中不含其它顶点若,存在,则存在路径{vi,v1,vj}//路径中所含顶点序号不大于1若{vi,…,v2},{v2,…,vj}存在,则存在一条路径{vi,…,v2,…vj}//路径中所含顶点序号不大于2…依次

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

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

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