#include <stdio.h>
#define  MAX_VERTEX_NUM  10
#define  INFINITY        1000

typedef struct Arc
{
    int weight;
}Arc, ArcMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef struct MGraph
{
    ArcMatrix   arcs;
    int vexnum;
    int arcnum;
}MGraph;

void CreateGraph(MGraph &G)
{
    int i, j, v1, v2, w;

    printf("Input the count of DGraph's vertexs:");
    scanf("%d", &G.vexnum);
    for(i = 0; i < G.vexnum; i++)
        for(j = 0; j < G.vexnum; j++)
            G.arcs[i][j].weight = INFINITY;

    printf("\nFollowing, input the infomation of each arc, enter -1 to exit:");
    G.arcnum = 0;

    while(1)
    {
        printf("\nInput the tail vertex of NO.%d arc:", G.arcnum);
        scanf("%d", &v1);
        if(v1 == -1)
            break;
        printf("Input the head vertex of NO.%d arc:", G.arcnum);
        scanf("%d", &v2);
        printf("Input the weight of NO.%d arc:", G.arcnum++);
        scanf("%d", &w);
        G.arcs[v1][v2].weight  = w;        
    }
}

int GetMinIndex(MGraph G, int dijk[], int used[])
{
    int i, min_index = -1, min = INFINITY;
    for(i = 1; i < G.vexnum; ++i)
        if(!used[i] && dijk[i] < min)
        {
            min = dijk[i];
            min_index = i;
        }

    return min_index;
}

void ShortestPathDij(MGraph G, int dijk[], int v0, int used[])
{
    int i, j, k;
    for(i = 0; i < G.vexnum; ++i)
        dijk[i] = G.arcs[v0][i].weight;
    dijk[v0] = 0;
    used[v0] = 1;

    for(i = 1; i < G.vexnum; ++i)
    {
        k = GetMinIndex(G, dijk, used);
        if(k == -1)
            return;
        used[k] = 1;
        for(j = 0; j < G.vexnum; ++j)
        {
            if(dijk[k] + G.arcs[k][j].weight < dijk[j])
                dijk[j] = dijk[k] + G.arcs[k][j].weight;
        }
    }
}

void main()
{
    int dijk[MAX_VERTEX_NUM], i;
    int used[MAX_VERTEX_NUM] = {0};
    MGraph  G;
    CreateGraph(G);
    ShortestPathDij(G, dijk, 0, used);
    for(i = 1; i < G.vexnum; ++i)
        printf("\nthe shortest path from v0 to v%d cost %d", i, dijk[i]);
}

谢谢