求的是arc数组中存储的第一个顶点到其他顶点的最短路径，结果存在dis数组中。
＃i nclude <stdio.h>
＃i nclude <malloc.h>
#define MAX 100
#define MAXNUM 10000000
typedef struct graphnode
{
int vexnum;
int arcnum;
int gra[MAX][MAX];
}Graph;
int dis[MAX];
int arc[MAX][MAX];
void bellman(Graph *g);
int main()
{
int i,j;
Graph *G;
G=(Graph *)malloc(sizeof(Graph));
printf("vexnum:\n");
scanf("%d",&G->vexnum);
printf("arcnum:\n");
scanf("%d",&G->arcnum);
printf("graph:\n");
for(i=0;i<G->vexnum;i++)
for(j=0;j<G->vexnum;j++)
scanf("%d",&G->gra[i][j]);
for(i=0;i<G->arcnum;i++)
{
printf("the %dth arc:\n");
scanf("%d%d",&arc[i][0],&arc[i][1]);
}
bellman(G);
return 0;
}
void bellman(Graph *G)
{
int i,j;
bool sign;
for(i=0;i<G->vexnum;i++)
dis[i]=MAXNUM;
dis[1]=0;
sign=true;
for(i=1;i<G->vexnum;i++)
{
sign=false;
for(j=0;j<G->arcnum;j++)
{
if(dis[arc[j][0]]<MAXNUM && dis[arc[j][1]]>dis[arc[j][0]]+G->gra[arc[j][0]][arc[j][1]])
{
dis[arc[j][1]]=dis[arc[j][0]]+G->gra[arc[j][0]][arc[j][1]];
sign=true;
}
}
}
return;
}
发表评论 
打印本文
推荐本文
加入收藏
返回顶部
关闭窗口
