求助求助。。帮忙帮忙。。拓扑问题。。最短路由路径
#include "string.h"#include "stdio.h"
#define INFINITY 9999
#define MAX_VERTEX_NUM 11
#define TRUE 1
#define FALSE 0
typedef struct{
char vex[MAX_VERTEX_NUM][5];
int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
int vexnum;
}MGraph;
typedef int PathMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef int ShortPathTable[MAX_VERTEX_NUM];
void ShortestPath_DIJ(MGraph G,int v0,PathMatrix &P,ShortPathTable &D)
{
int i,j,v,w,min,final[MAX_VERTEX_NUM];
for(v=0;v<G.vexnum;++v)
{
final[v]=FALSE; D[v]=G.arcs[v0][v];
for(w=0;w<G.vexnum;++w) P[v][w]=FALSE;
if(D[v]<INFINITY) {P[v][v0]=TRUE; P[v][v]=TRUE;}
}
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];
for(j=0;j<MAX_VERTEX_NUM;j++)
P[w][j]=P[v][j];
P[w][w]=TRUE;
}
}
}
void main()
{
int v0=0,i,j,n;
MGraph G={"R1","R2","R3","R4","R5","R6","N1","N2","N3","N4","N5",
0,9999,9999,8,9999,9999,5,9999,9999,9999,9999,
9999,0,9999,9999,4,9999,7,9999,9999,9999,9999,
9999,9999,0,9999,9999,9999,3,2,9999,9999,9999,
8,9999,9999,0,9999,9999,9999,9999,2,9999,9999,
9999,4,9999,9999,0,9999,9999,9999,5,2,9999,
9999,9999,9999,9999,9999,0,9999,9999,9,9999,5,
0,0,0,9999,9999,9999,0,9999,9999,9999,9999,
9999,9999,0,9999,9999,9999,9999,0,9999,9999,9999,
9999,9999,9999,0,0,0,9999,9999,0,9999,9999,
9999,9999,9999,9999,0,9999,9999,9999,9999,0,9999,
9999,9999,9999,9999,9999,0,9999,9999,9999,9999,0,
MAX_VERTEX_NUM };
PathMatrix P;
ShortPathTable D;
ShortestPath_DIJ(G,v0,P,D);
printf("开始路由器 目的路由器或目的网络 经过的路由器或网络序列 最短路径值\n");
for(i=1;i<MAX_VERTEX_NUM;i++)
{
printf(" %s %s ",G.vex[v0],G.vex[i]);
for(j=0,n=0;j<MAX_VERTEX_NUM;j++)
if(P[i][j]) //显示经过路径
{ printf(" %s ",G.vex[j]); n++; }
for(j=0;j<8-n;j++) //对齐
printf(" ");
printf("%d\n",D[i]);
}
printf("目的网络 下一跳(路由器)\n");
for(i=6;i<MAX_VERTEX_NUM;i++)
{
printf("%s ",G.vex[i]);
for(j=1;j<6;j++)
{
if(P[i][j]&&G.arcs[i][j]<9999)
printf(" %s",G.vex[j]);
}
printf("\n");
}
}
这个程序怎么判断输入是否符合拓扑要求。。。求修改、、、谢谢啦。。。。