2011年软考程序员考试复习笔试知识点整理(12)

来源:软件水平考试    发布时间:2012-11-05    软件水平考试视频    评论

  16、单源最短路径

  (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;

  }

视频学习

我考网版权与免责声明

① 凡本网注明稿件来源为"原创"的所有文字、图片和音视频稿件,版权均属本网所有。任何媒体、网站或个人转载、链接转贴或以其他方式复制发表时必须注明"稿件来源:我考网",违者本网将依法追究责任;

② 本网部分稿件来源于网络,任何单位或个人认为我考网发布的内容可能涉嫌侵犯其合法权益,应该及时向我考网书面反馈,并提供身份证明、权属证明及详细侵权情况证明,我考网在收到上述法律文件后,将会尽快移除被控侵权内容。

最近更新

社区交流

考试问答