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

作者：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<N;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();//出栈

}

}

}

补充：综合编程 , 其他综合 ,

上一个：代码重构-利用“反射机制”消除条件语句
下一个：《算法导论》学习总结 — 3.第四章 && 第五章