软件水平 > 初级资格 > 程序员 > 文章内容

计算机软考程序员常考基础必知必会(51)

2016-4-27编辑:ljnbset

单源最短路径

  (1)Dijkstra 算法可以用来解决非负权重网络的单源点最短路径。

  Dijkstra 算法的基本思想就是用贪心策略维护一棵最短路径生成树,先用dist[]数组维护一个最短路径,dist[v]表示起点 v0 与当前最短路径树中的顶点 v 的最短路径。选择下一个顶点时,我们找一条边 ,x 属于当前最短路径树中的点,y不属于当前最短路径树中的点,使得 dist[x]+ w(x,y) 最小,将边 加入到最短路径树中,依次进行,最后求得就是从起点 v0 出发的最短路径。

  最短路径 dijsktra 算法模板:

  #include

  usingnamespace std;

  constint maxint = 9999999;

  constint maxn = 1010;

  intdata[maxn][maxn];//data存放点点之间的距离,

  intlowcost[maxn]; //lowcost存放点到start的距离, 从0开始存放

  boolused[maxn];//标记点是否被选中

  intn; //顶点的个数

  voiddijkstra(int start)//初始点是start的dij算法

  {

  int i,j;

  memset(used, 0, sizeof(used));

  //init

  for(i = 0; i < n; i++)

  lowcost[i] = data[start][i];

  used[start] = true;

  lowcost[start] = 0;

  for(i = 0; i < n-1; i++)

  {

  //choose min

  int tempmin = maxint;

  int choose;

  for(j = 0; j < n; j++)

  {

  if(!used[j] && tempmin >lowcost[j])

  {

  choose = j;

  tempmin = lowcost[j];

  }

  }

  used[choose] = true;

  //updata others

  for(j = 0; j < n; j++)

  {

  if(!used[j] &&data[choose][j] < maxint && lowcost[choose]+data[choose][j]

  {

  lowcost[j] =lowcost[choose]+data[choose][j];

  }

  }

  }

  }

  intmain()

  {

  int start , i , j;

  cin>>n;

  for(i = 0; i < n; i++)

  for(j = 0; j < n; j++)//输入顶点信息

  {

  cin>>data[i][j];

  }

  cin>>start;

  dijkstra(start);

  int min = 0;

  for(i = 0; i < n; i++)

  {

  cout<

  for(i=0;i

  {

  for(j=0;j

  a[i][j]=MAX;

  for(i=0;i

  a[i][i]=0;

  while(edge_amount--)

  {

  scanf("%d%d%d",&i,&j,&w);

  a[i][j]=w;

  }

  Bellman_Ford(0);

  for(i=0;i

  {

  printf("dist:%d\t",d[i]);

  printf("path: %d",P[i]);

  printf("\n");

  }

  }

  return 0;

  }

计算机软考程序员常考基础必知必会(50)

热点推荐

登录注册
触屏版电脑版网站地图