这个算法的效率应该是理论上最好的了，因为要求出两点间所有的路径，必须考察每种可能（否则的话信息量不够），所以这个回溯法是唯一的方法。至于运算的速度，取决于你的图的规模和顶点的数目，这个算法的复杂度是O(VE)。内存耗光的问题一般不会出现，我试过用这个计算5000个节点的随机地图，速度还是蛮快的，一下子就出解了。该算法很简单，基本思想就是回溯。
#include<alloc.h>
#include<stdio.h>
#include<string.h>
#define NULL 0
#define MAX 100
struct edgenode
{int no;
struct edgenode *next;
};
struct vex
{struct edgenode *first;
};
typedef struct vex adjlist; //
int n,e; //
adjlist *g;
void initalize() //
{int i,s,t;
struct edgenode *p,*q;
printf("Enter the n and e:");
scanf("%d %d",&n,&e);
g=(adjlist *)malloc(n*sizeof(adjlist));
for(i=0;i<n;i++) g[i].first=NULL;
for(i=1;i<=e;i++)
{printf("The %d edge’s start and end:",i);
scanf("%d %d",&s,&t);
//p=(struct edgenode *)malloc(sizeof(struct edgenode));
q=(struct edgenode *)malloc(sizeof(struct edgenode));
//p->no=s;
q->no=t;
//p->next=g[t].first;g[t].first=p; 此句加上即可变为无向图。
q->next=g[s].first;g[s].first=q;
}
}
void path(int st,int en)
{int *visit,*stack,top,v,head=1,i;
struct edgenode *p;
visit=(int *)malloc(n*sizeof(int));
stack=(int *)malloc((n+1)*sizeof(int));
for(i=0;i<n;i++) visit[i]=0;
v=st;visit[st]=1;top=1;stack[top]=v;
do{if(head==1) {p=g[v].first;
head=0;}
else p=p->next;
if(p)
{if(visit[p->no]==0)
{visit[p->no]=1;
top++;
stack[top]=p->no;
if(p->no==en)
{for(i=1;i<=top;i++)
printf("%d ",stack[i]);
printf("\n");
visit[en]=0;
top--;
v=stack[top];
head=0;}
else {v=stack[top];
head=1;}
} //
}
else {visit[stack[top--]]=0; //
if(top)
{p=g[stack[top]].first;
while(p->no!=v) p=p->next;
v=stack[top];
head=0;}
}
}while(top);
}
main()
{int st,en; //
initalize();
printf("Enter the start and the end:");
scanf("%d %d",&st,&en);
path(st,en);
getchar();
getchar();
}