#include "stdio.h"
#include "stdlib.h"
#define N 6 // 顶点数
#define S 0 // 尚未求出最短路径
#define T 1 // 已经求出最短路径
#define M 10000

///////////////////////////////////////////////////////

void dijkstra(int cost[][N],int v,int dist[],char path[][N]); //计算v到其余各顶点的最短距离dist[]，最短路径path[N][N]
int mincost(int dist[],int set[]); //在S集合中找顶点w，dist[w]是dist[]中的最小值
void strcat(char path_j[],char path_w[],int w); // 合并路径

///////////////////////////////////////////////////////函数说明
void main()
{
int cost[N][N]={
{0 ,M ,10 ,M ,30 ,100},
{M ,0 ,5 ,M ,M ,M },
{M ,M ,0 ,50 ,M ,M },
{M ,M ,M ,0, M ,10 },
{M ,M ,M ,20 ,0 ,60 },
{100,M ,M ,M ,M ,M },
};

int dist[N]; char path[N][N]; /* 路径字符串 */
dijkstra(cost,0,dist,path); /* 起点为顶点0 */
}

//计算v到其余各顶点的最短距离dist[]，最短路径path[N][N]
void dijkstra(int cost[][N],int v,int dist[],char path[][N])
{ int set[N], i,j,nearest_v;
for(i=0; i<N; i++)
{ dist[i]=cost[v][i]; set[i]=S;
path[i][0]='\0'; /* 路径字符串初始化为空 */
}
for(set[v]=T,i=1; i<N; i++)
{
nearest_v=mincost(dist,set);
for(set[nearest_v]=T,j=0; j<N; j++)
if(set[j]==S && dist[nearest_v]+cost[nearest_v][j]<dist[j])
{
dist[j]=dist[nearest_v]+cost[nearest_v][j];
strcat(path[j],path[nearest_v],nearest_v); //合并路径
}
}
}

//在S集合中找顶点w，dist[w]是dist[]中的最小值/
int mincost(int dist[],int set[])
{
int i,min,w;
for(min=M,i=0; i<N; i++) /* N为顶点数 */
if(set[i]==S && dist[i]<min) { min=dist[i]; w=i; }
return(w);
}

// 合并路径
void strcat(char path_j[],char path_w[],int w)
{ int i;
for(i=0; path_w[i]!='\0'; i++) path_j[i]=path_w[i];
path_j[i++]=w+'0'; path_j[i]='\0';
}