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

《有向图中任意两点之间的最短路径》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

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

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

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

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

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

6、=1;i

7、∞30100∞∞5∞∞∞∞∞∞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}对于”每一对定点之间的最短路径问题”有经典算法――弗洛伊德算法从

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