主题:急!!!关于DIJKSTRA的问题。
最短路径问题:从家到十所高校的最短时间及最节省费用
我令堵车的时候,毎一条路径的权值(RowColWeight rcw1[])增加15,老师说这么做不符合实际情况,说应该分别对毎一条路径赋予不同的权值。请高手帮忙改一下,谢谢~~~
测试函数:
void main()
{
AdjMGraph g1,g2,g3;
char a[15]={'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O'};
char name[15][20]={"HOME\0","SHOU-SHI-DA\0","SHOU-JING-MAO\0","WAI-JIAO-XUE-YUAN","BEI-WAI\0","REN-DA\0","BEI-DA\0","BEI-HANG\0","BEI-SHI-DA\0","BEI-FU\0","BEI-GONG-DA\0","XI-ZHI-MEN\0","FU-CHENG-MEN","JIAN-GUO-MEN\0","DONG-ZHI-MEN\0"};
RowColWeight rcw2[]={{0,1,1},{0,3,0},{0,5,1},{0,7,2},{0,11,1},{0,12,1},{1,2,2},{1,4,1},{1,5,1},{4,5,1},{4,6,2},{5,6,1},{7,6,1},{8,9,1},{11,5,1},{11,6,2},{11,7,2},{11,8,1},{11,9,1},{11,14,3},{12,2,2},{12,8,1},{12,9,2},{12,13,3},{13,10,1},{14,9,1},{14,13,3}};
RowColWeight rcw1[]={{0,1,10},{0,3,5},{0,5,30},{0,7,40},{0,11,15},{0,12,15},{1,2,40},{1,4,10},{1,5,15},{4,5,10},{4,6,30},{5,6,30},{7,6,20},{8,9,15},{11,5,30},{11,6,40},{11,7,20},{11,8,20},{11,9,30},{11,14,10},{12,2,45},{12,8,30},{12,9,25},{12,13,20},{13,10,20},{14,9,15},{14,13,15}};
RowColWeight rcw3[]={{0,1,118},{0,3,0},{0,5,320},{0,7,392},{0,11,392},{0,12,709},{1,2,968},{1,4,968},{1,5,944},{4,5,374},{4,6,323},{5,6,323},{7,6,47},{8,9,708},{11,5,634},{11,6,604},{11,7,392},{11,8,44},{11,9,409},{11,14,000},{12,2,820},{12,8,709},{12,9,13},{12,13,000},{13,10,836},{14,9,831},{14,13,000}};
int i,n=15,e=27,k,y,t,m=0;
char x;
int distance1[15],distance2[15],path1[15],path2[15],distance3[15],path3[15];
CreatGraph(&g1,a,n,rcw1,e);
CreatGraph(&g2,a,n,rcw2,e);
CreatGraph(&g3,a,n,rcw3,e);
Dijkstra(g1,0,distance1,path1);
Dijkstra(g2,0,distance2,path2);
for(i=0;i<15;i++)
{
printf("%c==%s\n",a[i],name[i]);
}
printf("\n");
printf("NI DAO DA DE MU DI DI:");
scanf("%c",&x);
for(i=0;i<=14;i++)
{
if(a[i]==x)k=i;
}
printf("\n");
printf("XUAN ZE MO SHI: \n\n");
printf("'1'--min time\n");
printf("'0'--min money\n");
scanf("%d",&y);
if(y==1)
{
printf("The time you go out:");
scanf("%d",&t);
if(t>=0&&t<=5)
printf("CI SHI JIAN MEI YOU GONG JIAO CHE!\n");
else{ if(t>=7&&t<=9||t>=16&&t<=19)
{for(i=0;i<15;i++)
{
[color=FF00FF]rcw1[i].weight=rcw1[i].weight+15;[/color]
CreatGraph(&g1,a,n,rcw1,e);
Dijkstra(g1,0,distance1,path1);
}
}
printf("CONG JIA DAO '%c' DE ZUI DUAN SHI JIAN SHI %d\n\n",g1.Vertices.list[k],distance1[k]);
printf("the road is:\n\n");
while(k>0)
{
Dijkstra(g3,path1[k],distance3,path3);
printf("%c<--(%d)",g1.Vertices.list[k],distance3[k]);
k=path1[k];
}
printf("A\n===============================================================================================================================================================\n");
}
}
else if(y==0)
{
printf("CONG JIA DAO '%c' DE ZUI SHAO HUA FEI SHI $%d\n",g2.Vertices.list[k],distance2[k]);
printf("the road is:");
while(k>0)
{
Dijkstra(g3,path2[k],distance3,path3);
printf("%c<--(%d)",g2.Vertices.list[k],distance3[k]);
Dijkstra(g1,path2[k],distance1,path1);
m=distance1[k]+m;
k=path2[k];
}
printf("A\n");
printf("cost time:%d\n",m);
printf("\n~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n");
}
else printf("error!\n");
}
我令堵车的时候,毎一条路径的权值(RowColWeight rcw1[])增加15,老师说这么做不符合实际情况,说应该分别对毎一条路径赋予不同的权值。请高手帮忙改一下,谢谢~~~
测试函数:
void main()
{
AdjMGraph g1,g2,g3;
char a[15]={'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O'};
char name[15][20]={"HOME\0","SHOU-SHI-DA\0","SHOU-JING-MAO\0","WAI-JIAO-XUE-YUAN","BEI-WAI\0","REN-DA\0","BEI-DA\0","BEI-HANG\0","BEI-SHI-DA\0","BEI-FU\0","BEI-GONG-DA\0","XI-ZHI-MEN\0","FU-CHENG-MEN","JIAN-GUO-MEN\0","DONG-ZHI-MEN\0"};
RowColWeight rcw2[]={{0,1,1},{0,3,0},{0,5,1},{0,7,2},{0,11,1},{0,12,1},{1,2,2},{1,4,1},{1,5,1},{4,5,1},{4,6,2},{5,6,1},{7,6,1},{8,9,1},{11,5,1},{11,6,2},{11,7,2},{11,8,1},{11,9,1},{11,14,3},{12,2,2},{12,8,1},{12,9,2},{12,13,3},{13,10,1},{14,9,1},{14,13,3}};
RowColWeight rcw1[]={{0,1,10},{0,3,5},{0,5,30},{0,7,40},{0,11,15},{0,12,15},{1,2,40},{1,4,10},{1,5,15},{4,5,10},{4,6,30},{5,6,30},{7,6,20},{8,9,15},{11,5,30},{11,6,40},{11,7,20},{11,8,20},{11,9,30},{11,14,10},{12,2,45},{12,8,30},{12,9,25},{12,13,20},{13,10,20},{14,9,15},{14,13,15}};
RowColWeight rcw3[]={{0,1,118},{0,3,0},{0,5,320},{0,7,392},{0,11,392},{0,12,709},{1,2,968},{1,4,968},{1,5,944},{4,5,374},{4,6,323},{5,6,323},{7,6,47},{8,9,708},{11,5,634},{11,6,604},{11,7,392},{11,8,44},{11,9,409},{11,14,000},{12,2,820},{12,8,709},{12,9,13},{12,13,000},{13,10,836},{14,9,831},{14,13,000}};
int i,n=15,e=27,k,y,t,m=0;
char x;
int distance1[15],distance2[15],path1[15],path2[15],distance3[15],path3[15];
CreatGraph(&g1,a,n,rcw1,e);
CreatGraph(&g2,a,n,rcw2,e);
CreatGraph(&g3,a,n,rcw3,e);
Dijkstra(g1,0,distance1,path1);
Dijkstra(g2,0,distance2,path2);
for(i=0;i<15;i++)
{
printf("%c==%s\n",a[i],name[i]);
}
printf("\n");
printf("NI DAO DA DE MU DI DI:");
scanf("%c",&x);
for(i=0;i<=14;i++)
{
if(a[i]==x)k=i;
}
printf("\n");
printf("XUAN ZE MO SHI: \n\n");
printf("'1'--min time\n");
printf("'0'--min money\n");
scanf("%d",&y);
if(y==1)
{
printf("The time you go out:");
scanf("%d",&t);
if(t>=0&&t<=5)
printf("CI SHI JIAN MEI YOU GONG JIAO CHE!\n");
else{ if(t>=7&&t<=9||t>=16&&t<=19)
{for(i=0;i<15;i++)
{
[color=FF00FF]rcw1[i].weight=rcw1[i].weight+15;[/color]
CreatGraph(&g1,a,n,rcw1,e);
Dijkstra(g1,0,distance1,path1);
}
}
printf("CONG JIA DAO '%c' DE ZUI DUAN SHI JIAN SHI %d\n\n",g1.Vertices.list[k],distance1[k]);
printf("the road is:\n\n");
while(k>0)
{
Dijkstra(g3,path1[k],distance3,path3);
printf("%c<--(%d)",g1.Vertices.list[k],distance3[k]);
k=path1[k];
}
printf("A\n===============================================================================================================================================================\n");
}
}
else if(y==0)
{
printf("CONG JIA DAO '%c' DE ZUI SHAO HUA FEI SHI $%d\n",g2.Vertices.list[k],distance2[k]);
printf("the road is:");
while(k>0)
{
Dijkstra(g3,path2[k],distance3,path3);
printf("%c<--(%d)",g2.Vertices.list[k],distance3[k]);
Dijkstra(g1,path2[k],distance1,path1);
m=distance1[k]+m;
k=path2[k];
}
printf("A\n");
printf("cost time:%d\n",m);
printf("\n~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n");
}
else printf("error!\n");
}