#include <stdio.h> #include <stdlib.h> #include <string.h> #include <malloc.h> #define MAXV 1000 #define ElemType int #define INF 32767typedef struct { int no; int info; }VertexType; typedef struct{ int edges[MAXV][MAXV]; int n,e; VertexType vexs[MAXV]; }

MGraph;

void CreateMGraph(MGraph *G)
{
int i,j,k,w;
printf("请输入顶点数和边数：\n");
scanf("%d,%d",&(G->n),&(G->e));
for(i=0;i<G->n;i++)
{
printf("请输入第%d个顶点的编号和信息：\n",i+1);
scanf("%d,%d",&(G->vexs[i].no),&(G->vexs[i].info));
}
for(i=0;i<G->n;i++)
for(j=0;j<G->n;j++)
G->edges[i][j]=INF;
for(k=0;k<G->e;k++)
{
printf("请输入一条边的起点、终点和权值：\n");
scanf("%d,%d,%d",&i,&j,&w);
G->edges[i][j]=w;
G->edges[j][i]=w;
}
}

void ShortestPath_Dijkstra(MGraph G,int v0,int *D,int *P)
{
int final[MAXV];
int i,j,k,min;
for(i=0;i<G.n;i++)
{
final[i]=0;
D[i]=G.edges[v0][i];
P[i]=0;
}
D[v0]=0;
final[v0]=1;
for(i=1;i<G.n;i++)
{
min=INF;
for(j=0;j<G.n;j++)
if(!final[j]&&D[j]<min)
{
k=j;
min=D[j];
}
final[k]=1;
for(j=0;j<G.n;j++)
if(!final[j] && (min+G.edges[k][j]<D[j]))
{
D[j]=min+G.edges[k][j];
P[j]=k;
}
}
}

void DisplayResult(MGraph G,int v0,int *D,int *P)
{
int i,j,k;
printf("起点为%d的最短路径如下：\n",v0);
for(i=0;i<G.n;i++)
{
if(i!=v0)
{
printf("从%d到%d的最短路径长度为：%d，路径为：",v0,i,D[i]);
j=i;
while(P[j]!=0)
{
printf("%d<-",G.vexs[j].no);
j=P[j];
}
printf("%d\n",G.vexs[j].no);
}
}
}

int main()
{
MGraph G;
int v0=0;
int D[MAXV],P[MAXV];
CreateMGraph(&G);
ShortestPath_Dijkstra(G,v0,D,P);
DisplayResult(G,v0,D,P);
return 0;
}