求两点之间的距离,求两点之间所有路径的算法

作者：finallyly 出处：技术（如若转载请注明作者和出处）
最近在实现一个算法，算法之内有一个子算法是求有向图内两个定点（原点和目的点）之间的全部路径。在网上翻阅了大部分资料，发现给出的算法和代码要么只能解决DAG（有向无环图）的两定点之间所有路径问题，要么就是算法本身存在若干漏洞，连DAG图也无法解决。花费了一天的时间，自己写了个求简单有向图中（包括dag和非dag）两定点之间所有路径的算法，特共享出来。
文章将按如下组织，首先给出path的定义，其次给出dag的定义，然后给出算法的伪代码，之后是算法的C++实现以及实验结果。

1 Path的定义

Path的定义是建立在walk,基础上的。参见Bondy的《Graph Theory With Applications》

由上面的定义，我问可以得出path是一个结点和边交叠出现的序列，并且在这个序列中结点不能重复，边也不能重复。

2 DAG的定义

DAG（Directed Acyclic Graph）:即不存在环路的有向图。或者说是DFS过程中不出现回边(backc edge)的图。如图2-1就是一个DAG。更一般的有向图见图2-2

2‑1 DAG
++++++++++++++++++++++++++++++++++++++
第1条路径是：0-->1-->4-->11
第2条路径是：0-->1-->3-->11
第3条路径是：0-->1-->2-->6-->10-->11
第4条路径是：0-->1-->2-->6-->9-->11
第5条路径是：0-->1-->2-->5-->8-->11
第6条路径是：0-->1-->2-->5-->7-->11
++++++++++++++++++++++++++++++++++++++

2‑2 Digraph
该图对应的矩阵型存储格式为：

它的路径有：
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
第一条路径：0->1->2->3->4
第二条路径：0->1->2->4
第三条路径：0->1->3->2->4
第四条路径：0->1->3->4
第五条路径：0->1->4
第六条路径：0->2->1->3->4
第七条路径：0->2->1->4
第八条路径：0->2->3->1->4
第九条路径：0->2->3->4
第十条路径：0->2->4
第十一条路径：0->3->1->2->4
第十二条路径：0->3->1->4
第十三条路径：0->3->2->1->4
第十四条路径：0->3->2->4
第十五条路径：0->3->4
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

3 算法设计

待求解问题是“求原点和目的点之间的全部路径”，求解问题的第一步，我们需要确定这是一个P问题还是NP问题。对于P问题，可以直接设计算法；对于NP问题，则需要一些近似手段。值得庆幸的是这是一个P问题。算法最大复杂度为

证明如下：
假定有向图为N个节点的简单完全图，即每个节点都与其他N-1个节点有边相连。起始结点和结束节点确定，那么我们需要排列中间的N-2个节点，对于第一个非固定的节点，它有N-2种可能取值。。。以此类推得到上述答案。
求两定点之间的全部路径，其根本是一个涉及到搜索和回溯的问题。我们设计算法时所关心的首要问题是：按照何种顺序搜索和回溯才能保证路径可以不重不漏地被全部找到。
如下是算法设计部分
图的存储结构：邻接矩阵。Arcs
工作结构：结点栈 mystack;
状态保存结构：
（1） VertexStatus[]={0,0,0,1,1,…}。当结点未进栈或者已经出栈，则其对应的状态为0，否则状态为1；
（2） ArcStatus[][]={0,0,1,0,1…..}当且仅当边的两个结点都在栈外时，边的状态才为0，否则为1。
注意我们只所以设计如上结点、边两个状态存储结构，就是依据于path的定义，结点不重复，边不重复。具有边状态存储结构，也是我的算法与其他算法根本上的不同。
不失一般性，我们假设原点的编号最小为0,目标点的编号最大N。我们的问题转换成了，求最小编号的节点与最大编号的节点之间的所有路径。
Intial :
Paths={}//路径集合
VertexStatus[]={0};//全部置0
ArcStatus[][]={0};////全部置0
mystack.push(0);
VertexStatus[0]=1;
While(!mystack.empty())
{
Int elem= mystack.top();//获得栈顶元素
if(elem==N)//找到了一条路径
{
path=Traverse(mystack);
Paths.add(path);
VertexStatus[elem]=0;
UpdateArcStatus();//更新ArcStatus[][]，使得所有两个端点都不在栈内的边的状态为0
mystack.pop();//移除栈顶元素
}
else
{
i=0;
For(;i { if(VertexStatus[i]=0&&ArcStatus[elem][i]=0&&Arcs.contain(elem,i))
{
VertexStatus[i]=1;
ArcStatus[elem][i]=1;
Mystack.push(i);//入栈
break;
}
}
if(i=N)//该节点没有符合要求的后续节点
{
VertexStatus[elem]=0;
UpdateArcStaus();////更新ArcStatus[][]，使得所有两个端点都不在栈内的边的状为0
Mystack.pop();//出栈
}
}
}

Tags:  最短路径算法c 蚁群算法最短路径 最长路径算法 最短路径算法 求两点之间的距离

延伸阅读

• 2010-12-13-- 单源最短路径程序,最短路径的程序---学会如何调试
• 2010-11-25-- 我们在奔三的路上,在奔三的路上喷几句，怎么计算成功的最短路径？
• 2011-4-6-- 两点之间所有路径,求两点之间所有路径的算法(一)
• 2011-1-19-- 迪杰斯特拉算法,最短路径算法—Dijkstra(迪杰斯特拉)算法分析与实现(C/C++)
• 2009-2-12-- 最短路径算法:最短路径算法的Java实现
• 2008-12-10-- 单源最短路径:单源最短路径算法
• 2009-10-11-- 最短路径算法:图的点对最短路径算法(C++实现)
• 2009-2-12-- 最短路径算法:A* 算法求解最短路径
• 2009-10-11-- 最短路径:最短路径－－优先队列式分支界限法
• 2009-9-2-- arcgis最短路径:ArcGIS网络分析最短路径分析源代码(VB6.0)