最短路径！！（帮忙改一下，有一个错误，我改不出来！！）
#define INFINITY 10000#define MAX_VERTEX_NUM 32
#define MAX_ARC_NUM 50
#include<stdio.h>
#include<string.h>
typedef struct{
int v;
char city[20];
}VertexType;
typedef struct {
VertexType vex[MAX_VERTEX_NUM];
int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
int vexnum,arcnum;
}MGraph;
typedef int ShortPathTable[MAX_VERTEX_NUM];
typedef int PathMatrix[MAX_VERTEX_NUM];
void CreateDG(MGraph &G){
int i,j;
char string[][20]={"Beijing","Haerbin","Changchun","Shenyang","Tianjin","Dalian","HHHT","Yinchuan",
"WLMQ","Xining","Lanzhou","Xi'an","Taiyuan","Zhengzhou","Xuzhou","Shanghai",
"Nanjing","Hefei","Wuchang","Changsha","Chongqinh","Chengdu","Kunming","Guiyang",
"Zhuzhou","Nanchang","Hangzhou","Fuzhou","Shenzhen","Guangzhou","Liuzhou","Nanning"
};
G.vexnum=MAX_VERTEX_NUM;
G.arcnum=MAX_ARC_NUM;
for(i=0;i<G.vexnum;++i)
for(j=0;j<G.vexnum;++j)
G.arcs[i][j]=INFINITY;
for(i=0;i<MAX_VERTEX_NUM;i++)strcpy(G.vex[i].city,string[i]);
FILE *fp;
char filename[10];
int ch;
fp=fopen("graph.dat","r");
ch=fgetc(fp)-48;
while(!feof(fp)){
int i=0,j=0;
if(ch!=0)i=10*ch;
ch=fgetc(fp)-48;
i=i+ch;
ch=fgetc(fp)-48;
if(ch!=0)j=10*ch;
ch=fgetc(fp)-48;
j=j+ch;
G.arcs[i][j]=0;
ch=fgetc(fp)-48;
if(ch!=0)G.arcs[i][j]=1000*ch;
ch=fgetc(fp)-48;
G.arcs[i][j]+=100*ch;
ch=fgetc(fp)-48;
G.arcs[i][j]+=10*ch;
ch=fgetc(fp)-48;
G.arcs[i][j]+=ch;
ch=fgetc(fp)-48;
}
}
void ShortestPath_DIJ(MGraph G,int v0,PathMatrix &P,ShortPathTable &D){
int v,w,i,min;
bool final[MAX_VERTEX_NUM];
for(w=0;w<MAX_VERTEX_NUM;w++)P[w]=-1;
for(v=0;v<G.vexnum;++v){
final[v]=false;
D[v]=G.arcs[v0][v];
if(D[v]<INFINITY)P[v]=v0;
}
D[v0]=0;
final[v0]=true;
for(i=1;i<G.vexnum;++i){
min=INFINITY;
for(w=0;w<G.vexnum;++w)
if(!final[w])
if(D[w]<min){
v=w;
min=D[w];
}
final[v]=true;
for(w=0;w<G.vexnum;++w)
if(!final[w]&&(min+G.arcs[v][w]<D[w])){
D[w]=min+G.arcs[v][w];
P[w]=v;
}
}
}
void Output_ShortestPath(MGraph G,int v0,int vn,PathMatrix P,ShortPathTable D){
printf("from(%d)%sto(%d)%sthe shortest line%dkm。\n\t",v0,G.vex[v0].city,vn,G.vex[vn].city,D[vn]);
printf("zhe shortest line is:");
int t;
int i;
int a[MAX_VERTEX_NUM];
printf("%s-->",G.vex[v0].city);
for(i=0;i<MAX_VERTEX_NUM;i++)a[i]=-1;
for(t=P[vn],i=MAX_VERTEX_NUM-1;(t!=-1)&&(t!=v0);i--){
a[i]=t;
t=P[t];
}
for(i=0;i<MAX_VERTEX_NUM;i++){
if(a[i]==-1)i++;
else printf("%s-->",G.vex[a[i]].city);
}
printf("%s",G.vex[vn].city);
}
void main()
{
int v0,vn,ch=1;
ShortPathTable D;
PathMatrix P;
MGraph G;
printf(" \t\t\tmap is aready loaded graph relative city");
printf("\n ****************************************************************************\n");
printf("\t0Beijing\t1Haerbin\t2Changchun\t3Shenyang\n\t4Tianjin\t5Dalian\t6HHHT\t7Yinchuan\n\t8WLMQ\t9Xining\t10Lanzhou\t11Xian\n\t12Taiyuan\t13Zhengzhou\t14Xuzhou\t15Shanghai\n\t16Nanjing\t17Hefei\t18Wuchang\t19Changsha\n\t20Chongqinh\t21Chengdu\t22Kunming\t23Guiyang\n\t24Zhuzhou\t25Nanchang\t26Hangzhou\t27Fuzhou\n\t28Shenzhen\t29Guangzhou\t30Liuzhou\t31Nanning\n ");
printf("****************************************************************************\n");
printf("\n");
CreateDG(G);
while(ch){
printf("input zhe num of beginning city");
scanf("%d",&v0);
printf("input zhe num of ending city");
scanf("%d",&vn);
ShortestPath_DIJ(G,v0,P,D);
printf("\n****************************************************************************\n");
Output_ShortestPath(G,v0,vn,P,D);
printf("\n*****************************************************************************\n");
printf("\n\n");
printf("1 for continue\t0 for exit");
printf("\n");
scanf("%d",&ch);
}
}
