[科技论文网] http://www.scipapers.com    2007-12-01  

单源最短路径bellman-ford算法

求的是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;
}

    来源：

声明：本文由网友推荐或作者提交，版权归原作者所有，刊登此文仅为传播知识，展示研究成果，提高文章引用率。未经原作者授权，禁止用于任何形式的商业行为。科技论文网倡导尊重知识、尊重劳动、保护原创、知识共享。由于部分论文文章来于网络，文章作者不祥，请相关的原创作者与我们联系，以便加上您的署名。