马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。
您需要 登录 才可以下载或查看,没有账号?我要加入
x
#include<stdio.h>
#include<stdlib.h>
typedef struct Vnode{ //前驱和最短路径长度数组节点的结构
int lenth; //记录从起始点到该点的最短路径长度
int pv[255]; //记录最短路径中该节点的前驱
}Vnode;
int G[255][255];
int Path[20][255]={0}; //记录所有最短路径
int Pcount=0; //count记录最短路径的条数,level记录层数
void InitMap(Vnode *D,int v0) //初始化所以节点的前驱数组和最短路径长度
{
int final[256];
int v,lenth=0,count=0,flag=0,p,w;
for(v=0;v<256;v++)
{
final[v]=0; //初始化已访问节点数组,0表示未访问
for( p=0;p<256;p++) //初始化各个节点的前驱数组
D[v].pv[p]=0;
if(v!=v0)
{
D[v].lenth=G[v0][v]; //设置首节点到当前节点的路长
if(G[v0][v]==1)
{
D[v].pv[v0]=1;
final[v]=1; //将与首节点直接相连的节点设为已访问
count++; //count记录已访问节点数
}
}
else
{
D[v].lenth=0; //首节点的路长为0
final[v]=1; //首节点设为已访问
count++;
}
}
lenth=1; //记录当前层数,即当前节点到起始点的最短路径长度
while(count<256) //主循环生成各节点的最短路径长度和前驱节点数组
{
for(w=0;w<256;w++)
{
if(!final[w])
{
for(v=0;v<256;v++)
if(final[v]&&D[v].lenth==lenth)
{
if(G[v][w]==1&&(D[w].lenth<D[v].lenth+1))
{
flag=1;
D[w].lenth=D[v].lenth+1;
D[w].pv[v]=1;
}
if(G[v][w]==1&&(D[w].lenth==D[v].lenth+1))
D[w].pv[v]=1;
}
if(flag==1)
{
final[w]=1;
count++;
flag=0;
}
}
}
lenth++;
}
}
void InitPath(Vnode *D,int level,int v,int v0) //生成初始最短路径数组,每行表示一条最短路径
{int j;
if(v==v0)
{
Pcount++;
return;
}
for(j=0;j<256;j++)
{
if(D[v-1].pv[j]==1)
{
Path[Pcount][level]=j+1;
InitPath(D,level+1,j+1,v0);
}
}
}
void ChangePath(Vnode *D,int ve) //生成完整最短路径数组,将路径中为0的项填充为上一行对应项
{
int i=0,j=0;
for(i=0;i<Pcount;i++)
{
for(j=0;j<=D[ve-1].lenth;j++)
{
if(Path[j]==0)
Path[j]=Path[i-1][j];
}
}
}
void main()
{ FILE *fp;
if ((fp=fopen(" mydata.txt","r"))==NULL)
printf("cannot open file");
fread(G,1,256*256,fp);
Vnode D[256];
int v0,ve,lenth=0,level=1;
int i=0,j=0;
printf("Input the start node and the last node: ");
scanf("%d %d",&v0,&ve);
getchar();
InitMap(D,v0-1);
printf("The shortest pathes is: \n");
Path[0][0]=ve;
InitPath(D,level,ve,v0);
ChangePath(D,ve);
for(i=0;i<Pcount;i++)
{
for(j=D[ve-1].lenth;j>=0;j--)
printf("%d ",Path[j]);
printf("\n");
}
} |