#include<stdio.h>
#define MAX_VERTEX_NUM 50
#define INFINITY 300
typedef char VertexType[3];
typedef struct vertex
{
int adjvex;//顶￥点?编括?号?
VertexType data;//顶￥点?信?息￠
}Vertex_Type;//顶￥点?类え?型í
typedef struct graph
{
int Vertex_Num;//顶￥点?数簓
int Edge_Num;//边?数簓
Vertex_Type vexs[MAX_VERTEX_NUM];//顶￥点?数簓组哩?
int edges[MAX_VERTEX_NUM][MAX_VERTEX_NUM];// 边?的?二t维?数簓组哩? }AdjMatix;//图?的?邻ⅷ?接ï矩?阵ï类え?型í
int Create_Adjmatix(AdjMatix &g)
{
int i,j,k,b,t,w;
printf("请?输?入?图?的?顶￥点?数簓和í边?数簓：阰\n");
scanf("%4d%4d",&g.Vertex_Num,&g.Edge_Num);
for (i=0;i<g.Vertex_Num;i++)
{
printf("请?输?入?序î号?为a%d的?顶￥点?的?信?息￠：阰\n",i);
scanf("%s",g.vexs[i].data);
g.vexs[i].adjvex=i;
}
for (i=0;i<g.Vertex_Num;i++)
{
for(j=0;j<g.Edge_Num;j++)
g.edges[i][j]=INFINITY;
}
for(k=0;k<g.Edge_Num;k++)
{
printf("请?输?入?序î号?为a%d的?边?的?信?息￠：阰\n",k);
printf("起e点?号? 终?点?号? 权ā?值μ\n");
scanf("%4d%4d%4d",&b,&t,&w);
if(b<g.Vertex_Num&&t<g.Vertex_Num&&w>0)
g.edges[b][t]=w;
else
{printf("输?入?错洙?误ï！?");return 0;}
}
return 1;
}
void main()
{
int dist[MAX_VERTEX_NUM];
int path[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
int s[MAX_VERTEX_NUM];//存?放?源′点?集ˉ
int mindis,i,j,k,u,t;
int x=1;
int y;//循-环·变?量?
int z;//循-环·变?量?
AdjMatix g;
Create_Adjmatix(g);
for(j=0;j<g.Vertex_Num;j++)
for(t=0;t<g.Vertex_Num;t++)
path[j][t]=0;//path[][]置?初?值μ
for(i=0;i<g.Vertex_Num;i++)
{
dist[i]=g.edges[0][i];
s[i]=0;
if(dist[i]<INFINITY)
{
path[i][0]=x;
path[i][i]=x;
}
}
dist[0]=0;//到?自?己o的?距à离?设Θ?定¨为a零?
s[0]=1;//V0放?入?源′点?集ˉ合?
printf("迪?杰ü斯1特?拉?最?短ì路·径?求ï解a如?下?：阰\n");
//开a始?主ð循-环·
for(i=1;i<g.Vertex_Num;i++)
{ u=-1;
mindis=INFINITY;
for(j=0;j<g.Vertex_Num;j++)
{ if(s[j]==0&&dist[j]<mindis)
{
u=j;
mindis=dist[j];
}
}
if(u!=-1)
{
s[u]=1;//并￠入?顶￥点?集ˉ合?
for(j=0;j<g.Vertex_Num;j++)
{
if(s[j]==0&&g.edges[u][j]<INFINITY&&dist[u]+g.edges[u][j]<dist[j])
{
dist[j]=g.edges[u][j]+dist[u];
for(k=0;k<g.Vertex_Num;k++)
{
path[j][k]=path[u][k];
}
x++;
path[j][j]=x;
}
}
printf("起e点?%s到?终?点? %s的?最?短ì路·径?为a：阰",g.vexs[0].data,g.vexs[u].data);
for(y=1;y<g.Vertex_Num;y++)
{
for(k=0;k<g.Vertex_Num;k++)
{
if(path[u][k]==y)
printf("=>%s",g.vexs[k].data);
}
}
printf("\n");
printf("最?短ì路·径?长¤度è为a：阰%d",dist[u]);
printf("\n");
}
else
{
for(y=0;y<g.Vertex_Num;y++)
if(s[y]==0)
printf("顶￥点?%s到?顶￥点?%s没?有瓺路·径?\n",g.vexs[0].data,g.vexs[y].data);
}
}
}
运行结果如下：。