声振论坛

 找回密码
 我要加入

QQ登录

只需一步,快速开始

查看: 1738|回复: 0

[C/C++] 如何才能输出结果啊!!各位大侠,帮帮小妹吧!!!谢谢啦

[复制链接]
发表于 2010-4-11 19:19 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有账号?我要加入

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");
}  
}
回复
分享到:

使用道具 举报

您需要登录后才可以回帖 登录 | 我要加入

本版积分规则

QQ|小黑屋|Archiver|手机版|联系我们|声振论坛

GMT+8, 2024-5-19 10:35 , Processed in 0.105336 second(s), 17 queries , Gzip On.

Powered by Discuz! X3.4

Copyright © 2001-2021, Tencent Cloud.

快速回复 返回顶部 返回列表