void Dijkstra(MatrixGraph G)
{
int weight[VERTEX_MAX];
int path[VERTEX_MAX];
int tmpvertex[VERTEX_MAX];
int i,j,k,v0,min;
printf("\n input source num:");
scanf("%d",&v0);
v0--;
for(i=0;i<G.VertexNum;i++)
{
weight[i] = G.Edges[v0][i];
if(weight[i] < MAXVALUE && weight[i] > 0)
path[i] = v0;
tmpvertex[i] = 0;
}
tmpvertex[v0] = 1;
weight[v0] = 0;
for(i=0;i<G.VertexNum;i++)
{
min = MAXVALUE;
k=v0;
for(j=0;j<G.VertexNum;j++)
if(tmpvertex[j] == 0 && weight[j] < min)
{
min = weight[j];
k=j;
}
tmpvertex[k] = 1;
for(j=0;j<G.VertexNum;j++)
if(tmpvertex[j] ==0 && weight[k] + G.Edges[k][j] < weight[j])
{
weight[j] = weight[k] + G.Edges[k][j];
path[j] = k;
}
}
for(i=0;i<G.VertexNum;i++)
{
if(tmpvertex[i] == 1)
{
k = i;
while( k != v0)
{
j = k;
printf("%c < " ,G.Vertex[k]);
k = path[k];
}
printf("%c \n", G.Vertex[k]);
}
else
printf("%c<-%c:no path\n",G.Vertex[i],G.Vertex[v0]);
}
}
