C++分析研究  
C++
日历
<2013年12月>
24252627282930
1234567
891011121314
15161718192021
22232425262728
2930311234
统计
  • 随笔 - 92
  • 文章 - 4
  • 评论 - 4
  • 引用 - 0

导航

常用链接

留言簿

随笔档案

文章档案

搜索

  •  

最新评论

阅读排行榜

评论排行榜

 
  1.综述
 
   Dijkstra算法解决的是带权重的有向图上单源最短路径问题,该算法要求所有边的权重都为非负值。
 
   算法重复从结点集 V-S中选择最短路径估计最小的结点 u ,将 u 加入到集合 S ,然后对所有从 u 出发的边进行
 
   松弛操作(相当于遍历选出最小权值)。使用一个最小优先队列 Q 来保存结点集合。(代码实现中:设置一个标记数组)。迪科斯彻算法使用了广度优先搜索算法。算法解决的是有向图中单个源点到其他顶点的最短路径问题。sat答案
 
   迪克斯拉算法类似于广度优先算法,也类似于计算最小生成树的 Prim 算法。
 
   2.代码
 
   int Dijkstra(Graph G,int n,int s,int t, int path[])
 
   {
 
   int i,j,w,minc,d[max_vertexes],mark[max_vertexes];
 
   for (i=0;i<n;i++) mark[i]=0;
 
   for (i=0;i<n;i++)
 
   { d[i]=G[s][i];
 
   path[i]=s; }
 
   mark[s]=1;path[s]=0;d[s]=0;
 
   for (i=1;i<n;i++)
 
   {
 
   minc=infinity;
 
   w=0;
 
   for (j=0;j<n;j++)
 
   if ((mark[j]==0)&&(minc>=d[j])) {minc=d[j];w=j;}
 
   mark[w]=1;
 
   for (j=0;j<n;j++)
 
   if ((mark[j]==0)&&(G[w][j]!=infinity)&&(d[j]>d[w]+G[w][j]))
 
   { d[j]=d[w]+G[w][j];
 
   path[j]=w; }
 
   }
 
   return d[t];
 
   }
 
   3.理解
 
   代码中参数:
 
   G:
 
   图,用邻接矩阵表示
 
   n:
 
   图的顶点个数
 
   s:
 
   开始节点
 
   t:
 
   目标节点
 
   path[]:
 
   用于返回由开始节点到目标节点的路径
 
   返回值:
 
   最短路径长度
 
   注意:
 
   输入的图的权必须非负
 
   顶点标号从0开始
 
   用如下方法打印路径:
 
   i=t;
 
   while (i!=s)
 
   {
 
   printf("%d<--",i+1);
 
   i=path[i];
 
   }
 
   printf("%d\n",s+1);
 
   1.初始化:先初始化源点 s 的 d[]数组的值,即把与源点相连的点的权值赋给 d[] 数组。
 
   2.用了三个 for 循环,一个 for 循环里面镶嵌两个并列的 for 循环。第一个 for 循环和第二个 for 循环是找出当前要进行松弛的结点,第三个 for 循环进行松弛操作。
 
   3.第三个 for 循环中的
 
   [cpp] view plaincopy在CODE上查看代码片派生到我的代码片
 
   d[j]>d[w]+G[w][j]
 
   其中 d[j] 也包括 d[j] 取值为无穷大的情况,其真实性意义就是 j 点与源点不相连,直接把 d[j] 赋值为当前进行松弛的点 w 加上 w 到 j 点的权值。托福答案
 
 
posted on 2013-12-06 23:24 HAOSOLA 阅读(402) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


 
Copyright © HAOSOLA Powered by: 博客园 模板提供:沪江博客
PK10开奖 PK10开奖