Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1072539
  • 博文数量: 165
  • 博客积分: 3900
  • 博客等级: 中校
  • 技术积分: 1887
  • 用 户 组: 普通用户
  • 注册时间: 2007-04-06 15:15
文章分类

全部博文(165)

文章存档

2020年(3)

2019年(8)

2017年(2)

2016年(8)

2015年(14)

2013年(15)

2012年(32)

2011年(11)

2010年(14)

2009年(7)

2008年(20)

2007年(31)

分类:

2007-05-09 10:28:08

单源最短路径bellman-ford算法 

求的是arc数组中存储的第一个顶点到其他顶点的最短路径,结果存在dis数组中。

#i nclude
#i nclude

#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;ivexnum;i++)
  for(j=0;jvexnum;j++)
   scanf("%d",&G->gra[i][j]);
 for(i=0;iarcnum;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;ivexnum;i++)
  dis[i]=MAXNUM;
 dis[1]=0;
 sign=true;
 for(i=1;ivexnum;i++)
 {
  sign=false;
  for(j=0;jarcnum;j++)
  {
   if(dis[arc[j][0]]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;
}

阅读(1329) | 评论(0) | 转发(0) |
0

上一篇:没有了

下一篇:贪吃蛇游戏--结构化编程

给主人留下些什么吧!~~