#include<stdio.h>

  #define MAXSIZE 6

  #define INF  32767

  void Ppath(int path[],int i,int v0)//先序递归查找最短路径(源点为v0)上的顶点

  {

    int k;

    k=path[i];

     if(k!=v0)//顶点Vk不是源点V0时

    {

      Ppath(path,k,v0);//递归查找顶点Vk的前一个顶点

      printf("%d,",k);//输出顶点Vk

     }

   }

  void Dispath(int dist[],int path[],int s[],int v0,int n)//输出最短路径

  {

    int i;

    for(i=;i<n;i++)

    if(s[i]==)//顶点Vi在集合S中

    {

     printf("从%d到%d的最短路径长度为:%d,路径为:",v0,i,dist[i]);

     printf("%d,",v0);//输出路径上的源点v0;

     Ppath(path,i,v0);//输出路径上的中间顶点vi

     printf("%d\n",i);//输出路径上的终点

      }

    else

   printf("从%d到%d不存在路径\n",v0,i);

 }

 void Dijkstra(int gm[][MAXSIZE],int v0,int n)//Dijkstra算法

 {

   int dist[MAXSIZE],path[MAXSIZE],s[MAXSIZE];

   int i,j,k,mindis;

   for(i=;i<n;i++)

   {

    dist[i]=gm[v0][i];//v0到vi的最短路径初值赋给dist[i]

    s[i]=;//s[i]=0表示顶点vi属于T集

    if(gm[v0][i]<INF)//路径初始化,INF为可取的最大常数

     path[i]=v0;

    else

     path[i]=-;//v0到vi没有边

 }

 s[v0]=;path[v0]=;//V0并入集合S且V0当前最短路径中无前一个顶点

 for(i=;i<n;i++)//对除V0外的n-1个顶点寻找最短路径,即循环n-1次

  {

   mindis=INF;

   for(j=;j<n;j++)//从当前集合T中选择一个路径长度最短的顶点Vk

   if(s[j]==&&dist[j]<mindis)

   {

    k=j;

   mindis=dist[j];

   }

  s[k]=;//顶点Vk加入集合S中

   for(j=;j<n;j++)//调整源点v0到集合T中任一顶点Vj的路径长度

    if(s[j]==)//顶点vj在集合T中

     if(gm[k][j]<INF&&dist[k]+gm[k][j]<dist[j])//当V0到Vj的路径长度小于V0到Vk和Vk到Vj的路径长度时

     {

      dist[j]=dist[k]+gm[k][j];

      path[j]=k;//Vk是当前最短路径中Vj的前一个顶点

      }

   }

  Dispath(dist,path,s,v0,n);//输出最短路径

 }

 void main()

 {

  int g[MAXSIZE][MAXSIZE]={{INF,,,INF,INF,INF},{,INF,INF,INF,,},{INF,,INF,INF,INF,},

                                           {INF,INF,INF,INF,INF,INF},{INF,INF,INF,,INF,INF},{INF,INF,INF,,,INF}};//定义邻接矩阵g

 Dijkstra(g,,);//求顶点0的最短路径

 }