【正确答案】本题属于基础题，考查图的创建和迪杰斯特拉算法。 int cost[maxSize][maxSize]; //cost为带权邻接矩阵 int dist[maxSize],n; //dist为从V0到各顶点的最短路程 struct { int num; int pnode[maxSize]; } path[maxSize]; //path为从V0到各顶点的最短路径 void creatgraph() //创建带权无向图 { int it j,s,e,len,contin=1; cout＜＜"顶点个数: "; cin＞＞n; for(i=0;i＜n;++i) { for(j=0;j＜n;++j) cost[i][j]=cost[j][i]=up; //up是已定义的最大值，表示无穷大 cost[i][i]=0; } cout＜＜"输入各边，以0，0，0表示结束：/n"; i=1: while(contin==1) { cout＜＜"/t第"＜＜i＜＜"条边-＞顶点，顶点，边长: "; cin＞＞s＞＞e＞＞len; if(s==0 && e==0 && len==0) contin=0; else { cost[s][e]=len; ++i; } } } void shortdjs() //求最短路径 { int s[maxSize]; int mindisfdis,i,j,v0=0,u; for(i=0;i＜n;++i) { dist[i]=cost[v0][i]; path[i].pnode[0]=v0; path[i].num=0; s[i]=0; } s[v0]=1; for(i=1;i＜n; ++i) { mindis=up; for(j=1;j＜n;++j) if(s[j]==0 && dist[j]＜mindis) { u=j; mindis=dist[j]; } s[u]=1; for(j=1;j＜n; ++j) if(s[j]==0) { dis=dist[u]+cost[u][j]; if(dist[j]＞dis) { dist[j]=dis; ++(path[j].num); path[j].pnode[path[j].num]=u; } } ++(path[i].num);/*将终点i添加到路径中*/ path[i].pnode[path[i].num]=i; } } void dispath() //输出最短路径 { int i,j; for(i=1;i＜n; ++i) { if(dist[i]＜up) cout＜＜dist[i]; else cout＜＜"∝"; //显示无穷大 for(j=0;j＜path[i].num; ++j) cout＜＜"V"＜＜path[i].pnode[j]＜＜","; } }