迪杰斯特拉算法 用邻接表存储无向网，最后怎么输出最短路径。

我已经能算出最短路径长度，但是不知道怎么输出最短路径，求教怎么修改！
#include<stdio.h>
#include<stdlib.h>
#define MAX_VERTEX_NUM 15
#define OK  1
#define ERROR 0
#define MAX_VALUE 1000//代表无穷


typedef int InfoType;       /* 该弧相关信息的指针类型 */
typedef char VertexType;      /* 顶点的类型 */

/*定义辅助表 用于记录最短路径*/
typedef struct
{
    int style;//标记是否在最短路径中 如果在职位1 否则为0
    int length;//记录最短的路径大小
}DIJ_table;




typedef struct ArcNode       /* 弧结点的结构 */
{
    int    adjvex;      /* 该弧所指向的顶点的位置 */
    struct ArcNode *nextarc;     /* 指向下一条弧的指针 */
    InfoType  info;      /* 该弧相关信息的指针（觉得应该是记录某些备注信息）如权值 */
}ArcNode;

typedef struct VNode       /* 顶点结点的结构 */
{
    VertexType data;       /* 顶点信息 */
    ArcNode  *firstarc;      /* 指向第一条依附该顶点的弧的指针 */
}VNode, AdjList[MAX_VERTEX_NUM];

typedef struct         /* 图的邻接表结构定义 */
{
    AdjList vertices;       /* 存放顶点的数组 */
    int  vexnum, arcnum;      /* 图的当前顶点数和弧数 */
   
}ALGraph;

void menu()
{
    printf("\t******************************************\n");
    printf("\t*         1 建立无向网                   *\n");
    printf("\t*         2 打印无向网                   *\n");
    printf("\t*         3 输出最短路径和长度           *\n");
    printf("\t*         4 退出程序                     *\n");
    printf("\t******************************************\n");
}


int LocateVex(ALGraph *G,char v)  /*存储顶点*/
{
    int i;
    for(i=1;i<=G->vexnum;i++)
        if(G->vertices[i].data == v)
            return i;
}

int CreateUDN(ALGraph &G)       /* 邻接表建立无向网 */
{  
    int   i,w,postion1,postion2;
    char s,d;
    ArcNode   *p,   *q;
    fflush(stdin);
    printf("请输入结点数和边数：\n");
    scanf("%d%d",&G.vexnum,&G.arcnum);    /* 输入结点数目和边数 */
   
    for(i=1;   i<=G.vexnum;   i++)     /* 输入顶点 */
    {
        fflush(stdin);
        printf("输入顶点:\n");
        scanf("%c",&G.vertices[i].data);   /* 输入顶点 */
        G.vertices[i].firstarc   =   NULL;   /* 首先初始化为NULL */
    }  
    for(i=1;   i<=G.arcnum;   i++)  
    {   
        fflush(stdin);
        printf("输入一条边依附的起点、终点和权值:\n");
        scanf("%c,%c,%d",&s,&d,&w);     /* 输入一条边依附的起点和终点 */
      
        p   =   (struct   ArcNode   *)malloc(sizeof(struct   ArcNode));  
        q   =   (struct   ArcNode   *)malloc(sizeof(struct   ArcNode));  
   
        postion1=LocateVex(&G,s);
        postion2=LocateVex(&G,d);

        p->adjvex   =   postion2;   /* 保存该弧所指向的顶点位置 */
        q->adjvex   =   postion1;   /* 保存该弧所指向的顶点位置 */
          p->info = w;   /* 保存权值到一个结点里 */
        q->info = w;   /* 保存权值到一个结点里 */
      
          p->nextarc   =   G.vertices[postion1].firstarc;  
        G.vertices[postion1].firstarc   =   p;
   
        q->nextarc   =   G.vertices[postion2].firstarc;  
        G.vertices[postion2].firstarc   =   q;  
     }
    return OK;
}   

void PrintALGraphUDN(ALGraph *G)      /* 打印无向网每个结点的单链表 */
{
    int i;
    ArcNode   *p;
    printf("打印无向网\n");
   

    for(i = 1 ; i <= G->vexnum ; i++)
    {
        printf("  %3c",G->vertices[i].data );
        if(G->vertices[i].firstarc  ==NULL)
        {
            printf("∧\n");
        }
        else
            printf(" --->> ");
        p=G->vertices[i].firstarc ;
      
        while(p)
        {
           
            printf("%3d%3d",p->adjvex,p->info);
            if(p->nextarc==NULL)
            {
                printf("∧\n");
            }
            else
                printf(" --->> ");
            p=p->nextarc;
      
        }
   
    }

}


/*在D_tabel表中查找没有加入到最短路径集合中最小的值 返回其下标*/
int Search_Min(int size,DIJ_table *D_table)
{
   
    int i=0, j=0;
    D_table[0].length = MAX_VALUE;//初始化

    for( i=1; i<=size; ++i )
    {
        if(!D_table[i].style)
        {//表示没有加入到最短路径集合中
            if( D_table[i].length <= D_table[0].length )
            {
                j = i;
                D_table[0].length = D_table[i].length;
            }
        }
    }
    D_table[j].style = 1;//在此处改成 加入到最短路径集合中 状态

    return j;
}

void ShortestPath_DIJ(ALGraph &G, int v0,DIJ_table *D_table)//v0表示要求的原点在向量表中的下标值
{
    int i=0, j=0;
    ArcNode *p;


    for( i=1; i<=G.vexnum; ++i )
    {
        D_table[i].style = 0;//所有的顶点初始化成没有被加入到最短路径集合中
        D_table[i].length = MAX_VALUE;//开始初始化成所有的最短路径为无穷即不可达状态
    }
    D_table[v0].length = 0;//处理开始的顶点 表示最短路径大小值为0  (v0 到 v0)
    for( i=2; i<=G.vexnum; ++i )
    {//根据算法表示要循环 vexnum - 1 次
        j = Search_Min(G.vexnum,D_table);//查找最小值 并返回最小值的下标 送j

        for( p=G.vertices[j].firstarc ; p!=NULL; p=p->nextarc )
        {
            if( D_table[p->adjvex].length  > D_table[j].length + p->info )
            {
                D_table[p->adjvex].length = D_table[j].length + p->info ;
            }
        }
    }
}

void Print_Path(ALGraph &G, int size,DIJ_table *D_table)
{

    int i;
    for(i=1;i<G.vexnum+1 ;i++)
    {
        printf("%3c",G.vertices[i].data);
   
    }
    printf("\n");
    for( i=1; i<=size; ++i )
        printf("%3d", D_table[i].length );

    printf("\n");
}



void main()
{
    DIJ_table D_table[MAX_VERTEX_NUM];
    char v;
    int v0;
    ALGraph G;
   
    int choice;
    while(1)
    {
        menu();
        printf("\t请选择一个菜单项：");
        scanf("%d",&choice);

        switch(choice)
        {
        case 1:
            CreateUDN(G);    /* 建立无向网 */
            break;
        case 2:
            PrintALGraphUDN(&G);    /* 打印无向网 */
            break;
        case 3:
            printf("请输入其实节点：\n");
            fflush(stdin);
            scanf("%c",&v);
            v0=LocateVex(&G,v);

            printf("\n");
            ShortestPath_DIJ( G, v0,D_table);

            Print_Path( G,G.vexnum ,D_table);
            break;
        case 4:
            exit(0);
            break;
        default:
            printf("\t您输入的菜单项不存在，请重新选择！\n");
        }
    }
   
}