一个有问题的最少上车次数程序
请有知识之士帮忙看下,程序可以运行,但是有结果怪怪的,不知道哪里出了问题!!!!#include <stdio.h>
#include <stdlib.h>
#define INFINITY 9999
#define MAXVNUM 30
int start,end;
typedef struct{
int Vnum;
int arcs[MAXVNUM][MAXVNUM];
}Graph;
int createGraph(Graph g)
{ int n,m,i,j,k,s,count;
int t[MAXVNUM];
printf("输入旅游景点数目和公交线路条数:\n");
printf("旅游景点数目=");
scanf("%d",&n);
printf("公交线路条数=");
scanf("%d",&m);
if(n<=1||m<1)
return -1;
printf("输入起始景点编号和终止景点编号:\n");
printf("起始景点=");
scanf("%d",&start);
printf("终止景点=");
scanf("%d",&end);
if(start<0 || start>n-1 || end<0 || end>n-1)
return -1;
g.Vnum=n;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
g.arcs[i][j]=INFINITY;
for(s=0;s<m;s++)
{ printf("请输入第%d条公交线路途径各景点的编号: \n",s+1);
scanf("%d",&k);
count=0;
while(k!=-1)
{
t[count++]=k;
scanf("%d",&k);
}
for(i=0;i<count-1;i++)
for(j=i+1;j<count;j++)
g.arcs[t[i]][t[j]]=1;
}
return 0;
}
int findMinmum(Graph g,int start,int end)
{ int s[MAXVNUM];
int i,j,u,*dist;
int min;
if(start==end)
return 0;
dist=(int *)malloc(sizeof(int));
if(dist==NULL)
return -1;
for(i=0;i<g.Vnum;i++)
{ dist[i]=g.arcs[start][i];
s[i]=0;
}
s[start]=1;
dist[start]=0;
for(i=0;i<g.Vnum;++i)
{ min=INFINITY;
u=start;
for(j=0;j<g.Vnum;++j)
if(s[j]==0 && dist[j]<min)
{ min=dist[j];
u=j;
}
s[u]=1;
for(j=0;j<g.Vnum;++j)
if(s[j]==0 && min+g.arcs[u][j]<dist[j])
dist[j]=min+g.arcs[u][j];
}
return dist[end];
}
int main(void)
{ int m;
Graph G;
if(createGraph(G)==-1)
{ printf("创建有向图失败!\n");
return -1;
}
m=findMinmum(G,start,end);
if(m<INFINITY)
printf("\n 从景点%d到%d的最少换车次数为: %d",start,end,m-1);
else
printf("\n无解！");
return 0;
}
[[it] 本帖最后由 风弄无声 于 2008-6-1 16:01 编辑 [/it]]
[[it] 本帖最后由 风弄无声 于 2008-6-1 16:23 编辑 [/it]]
