#define MaxVertexNum 100 #define INFITY 200 typedef int EdgeType; typedef char VertexType; typedef int pathMatrix; typedef int distancMatrix; typedef struct{ VertexType vexs[MaxVertexNum]; EdgeType edges[MaxVertexNum][MaxVertexNum]; int n,e; }MGraph; void shortest_path(MGraph *G,pathMatrix p[MaxVertexNum][MaxVertexNum],distancMatrix D[MaxVertexNum][MaxVertexNum]) /* 最短路径主算法*/ { int v,w,u,i,j; for(v=0;v<G->n;++v) for(w=0;w<G->n;++w) {D[v][w]=G->edges[v][w]; if(D[v][w]<INFITY&&D[v][w]!=0) p[v][w]=v; else if(v!=w) p[v][w]=-2; if(v==w) p[v][w]=-1; } for(u=0;u<G->n;++u) for(v=0;v<G->n;++v) for(w=0;w<G->n;++w) if(D[v][u]+D[u][w]<D[v][w]) {D[v][w]=D[v][u]+D[u][w]; p[v][w]=u; } for(i=0;i<G->n;i++) for(j=0;j<G->n;j++) { if(p[i][j]==i) printf("%c-->%c\n",G->vexs[i],G->vexs[j]); else if(p[i][j]>=0) printf("%c-->%c-->%c\n",G->vexs[i],G->vexs[p[i][j]],G->vexs[j]); /*输出*/ } } main() {MGraph *G; pathMatrix p[MaxVertexNum][MaxVertexNum]; distancMatrix D[MaxVertexNum][MaxVertexNum]; int i,j,k,w,m;clrscr(); G=(MGraph *)malloc(sizeof(MGraph));

printf("please input the numbers of the n and e:\n"); scanf("%d,%d",&(G->n),&(G->e));

printf("please input vertex:\n"); for(i=0;i<G->n;i++) scanf("\n%c",&(G->vexs[i]));

for(i=0;i<G->n;i++) for(j=0;j<G->n;j++) {if(i==j)G->edges[i][j]=0; else G->edges[i][j]=INFITY;}

for(k=0;k<G->e;k++) {printf("Input Vertex(e.g:i,j):\n"); scanf("%d,%d",&i,&j); printf("Input the edges of(%d,%d):\n",i,j); scanf("%d",&m); G->edges[i][j]=m; } /*初始化邻接矩阵*/

shortest_path(G,p,D); getch(); } 这是个图论问题, 整个程序都可以运行, 就是最后输出的那部分,我做不出来... 我那种输出好像错了. 就是只能输出两点或者是三点的最短路径, 无法输出四点,或者是五点.. 寻求解决之道...