程序代码：

#include <stdio.h>

/*
vertex 顶点 source 源点
path length 路径长度
pioneer 前驱
adjacent matrix 邻接矩阵
*/
#define MaxSize 5

#define Infinity 1000

void Dijkstra(int vertex, int source, int PathLength[], int AdjacentMatrix[MaxSize][MaxSize],int pioneer[MaxSize])
{
    //标记顶点是否在集合S中，如果是，则值为1，否为0
    int sign[vertex], i, j;

    for(i=0; i<vertex; i++)
    {
        //初始化源点到其他各个顶点的最短路径长度
        PathLength[i]=AdjacentMatrix[source][i];

        sign[i]=0;

        //满足条件，说明顶点i与源点不相邻
        if(PathLength[i]==Infinity)
        {
            pioneer[i]=-1;

        }
        else
        {
            pioneer[i]=source;
        }

    }

    //初始化时，集合S中只有一个元素，源点
    PathLength[source]=0;
    sign[source]=1;

    for(i=0; i<vertex; i++)
    {
        int temp=Infinity;

        int t=source;




        for(j=0; j<vertex; j++)
        {
            if((!sign[j]) && (PathLength[j]<temp))
            {
                t=j;
                temp=PathLength[j];
            }
        }

        if(t==source) break;

        sign[t]=1;


        for(j=0; j<vertex; j++)
        {
            if((!sign[j]) && (AdjacentMatrix[t][j]!=Infinity))
            {
                if(PathLength[j]>(PathLength[t]+AdjacentMatrix[t][j]))
                {

                    PathLength[j]=PathLength[t]+AdjacentMatrix[t][j];
                    pioneer[j]=t;
                }
            }
        }

    }


}

void find(int pineer[MaxSize], int i, int AdjacentMatrix[MaxSize][MaxSize])
{
    while(pineer[i]!=-1)
    {
        //反向的
        printf("(%d, %d)%d ", pineer[i], i, AdjacentMatrix[pineer[i]][i]);
        i=pineer[i];
    }
}

int main(void)
{
    int AdjacentMatrix[MaxSize][MaxSize]={Infinity,8,32,Infinity,Infinity,
                            12,Infinity,16,15,Infinity,
                            Infinity,29,Infinity,Infinity,13,
                            Infinity,21,Infinity,Infinity,7,
                            Infinity,Infinity,27,19,Infinity
                            };
    int vertex=MaxSize, i;

    int source=3;

    int PathLength[MaxSize];

    int pioneer[MaxSize];//记录前顶点

    for(i=0; i<MaxSize; i++)
    {
        //初始化前顶点为无穷大
        pioneer[i]=Infinity;
    }

    printf("请输入源点(0~4)：");

    scanf("%d", &source);

    printf("\n最短路径和长度\n");

    Dijkstra(vertex, source, PathLength, AdjacentMatrix, pioneer);

    for(i=0; i<vertex; i++)
    {
        if(i==source) continue;

        printf("\n源点%d到顶点%d : %d ", source, i, PathLength[i]);
        find(pioneer, i, AdjacentMatrix);
        printf("\n");
    }


    return 0;
}