#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");
    }
    }
这个程序怎么判断输入是否符合拓扑要求。。。求修改、、、谢谢啦。。。。

看了你上一个帖子，汗，不就是DIJKSTRA算法求单源最短路，建议看看算法导论，里面算法讲的很清楚
如果优先队列不懂的话可以不用，笨方法实现也可以，数据量不是很大的话时间还是过得去

我看了。。看不懂。。是因为编程实验我抽到了这道题。。有要求就是用拓扑图输入。。那个我一点都不会