pta最短路径迪杰斯特拉算法程序填空

以下是PTA最短路径迪杰斯特拉算法程序的填空代码：

#include <stdio.h>
#include <stdlib.h>
#define MaxVertexNum 501
#define INFINITY 65535

typedef int Vertex;
typedef int WeightType;
typedef char DataType;

typedef struct GNode *PtrToGNode;
struct GNode{
    int Nv;
    int Ne;
    WeightType G[MaxVertexNum][MaxVertexNum];
    DataType Data[MaxVertexNum];
};
typedef PtrToGNode MGraph;

typedef struct ENode *PtrToENode;
struct ENode{
    Vertex V1, V2;
    WeightType Weight;
};
typedef PtrToENode Edge;

MGraph CreateGraph( int VertexNum )
{
    Vertex V, W;
    MGraph Graph;

    Graph = (MGraph)malloc(sizeof(struct GNode));
    Graph->Nv = VertexNum;
    Graph->Ne = 0;
    for (V=0; V<Graph->Nv; V++)
        for (W=0; W<Graph->Nv; W++)
            Graph->G[V][W] = INFINITY;

    return Graph;
}

void InsertEdge( MGraph Graph, Edge E )
{
    Graph->G[E->V1][E->V2] = E->Weight;
    Graph->G[E->V2][E->V1] = E->Weight;
}

MGraph BuildGraph()
{
    MGraph Graph;
    Edge E;
    int Nv, i;

    scanf("%d", &Nv);
    Graph = CreateGraph(Nv);

    scanf("%d", &(Graph->Ne));
    if ( Graph->Ne != 0 ) {
        E = (Edge)malloc(sizeof(struct ENode));
        for (i=0; i<Graph->Ne; i++) {
            scanf("%d %d %d", &E->V1, &E->V2, &E->Weight);
            E->V1--;
            E->V2--;
            InsertEdge( Graph, E );
        }
    }

    return Graph;
}

void PrintDist( WeightType dist[], int N )
{
    int i;
    for ( i=0; i<N; i++ )
        printf("%d ", dist[i]);
}

void PrintPath( int path[], int V )
{
    if ( path[V] != -1 ) {
        PrintPath( path, path[V] );
        printf(" %d", V);
    } else
        printf("%d", V);
}

void Dijkstra( MGraph Graph, WeightType dist[], int path[], Vertex S )
{
    int collected[MaxVertexNum];
    Vertex V, W, MinV;
    WeightType MinDist;

    for ( V=0; V<Graph->Nv; V++ ) {
        dist[V] = Graph->G[S][V];
        if ( dist[V]<INFINITY )
            path[V] = S;
        else
            path[V] = -1;
        collected[V] = 0;
    }
    dist[S] = 0;
    collected[S] = 1;

    while (1) {
        MinDist = INFINITY;
        MinV = -1;
        for ( V=0; V<Graph->Nv; V++ ) {
            if ( collected[V]==0 && dist[V]<MinDist ) {
                MinDist = dist[V];
                MinV = V;
            }
        }
        if (MinV==-1) break;
        collected[MinV] = 1;
        for( W=0; W<Graph->Nv; W++ ) {
            if ( collected[W]==0 && Graph->G[MinV][W]<INFINITY ) {
                if ( Graph->G[MinV][W]<0 ) {
                    printf("Error: Negative Dist!\n");
                    return;
                }
                if ( dist[MinV]+Graph->G[MinV][W] < dist[W] ) {
                    dist[W] = dist[MinV]+Graph->G[MinV][W];
                    path[W] = MinV;
                }
            }
        }
    }
}

int main()
{
    int i;
    WeightType dist[MaxVertexNum];
    int path[MaxVertexNum];
    MGraph G = BuildGraph();

    Vertex S = 0;
    Dijkstra( G, dist, path, S );

    for ( i=1; i<G->Nv; i++ ) {
        printf("%d\n", dist[i]);
    }

    return 0;
}