首页 > 编程语言 > 详细

设计一个算法,输出从u到v的所有最短路径(采用邻接表存储)

时间:2015-07-18 14:12:01      阅读:355      评论:0      收藏:0      [点我收藏+]

思想:用path数组存放路径(初始为空),d表示路径长度(初始为-1),查找从顶点u到v的最短路径过程如图所示:

技术分享


















对应算法如下:

void FindPath(AGraph *G,int u,int v,int path[ ],int d)

{

int w,i;

ArcNode *p;

d++;

path[d]=u;

visited[u]=1; //路径长度增1

if(u==v)

{

for(i=0;i<=d;i++)

printf("%2d",path[i]);

printf("\n");

}

p=G->adjlist[u].firstarc; //p指向v的第一个相邻点

while(p!=NULL)

{

w=p->adjvex;

if(visited[w]==0) //若w顶点未访问,递归访问它

FindPath(G,w,v,path,d);

p=p->nextarc; //p指向v的下一个邻接点

}

visited[u]=0; //恢复环境,使该顶点可重新使用

}

版权声明:本文为博主原创文章,未经博主允许不得转载。

设计一个算法,输出从u到v的所有最短路径(采用邻接表存储)

原文:http://blog.csdn.net/wuruiaoxue/article/details/46940935

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!