32个重要算法之Dijkstra算法

3270阅读　0评论2013-10-31　bl竹子
分类：C/C++

我们首先给出一个用dijkstra求解问题的例子，然后给出dijkstra算法的具体过程。
问题是这样的：一个n位正整数a，删去其中的k位，得到一个新的正整数b，对给定的a和k，得到最小的b。
对于这个问题，可以用dijkstra算法来求解，源节点为n位的整数a，目的节点为(n-k)位的整数b，其它节点大致是这样的：有(n-1)个(n-1)位数组成的节点，有(n-1)*(n-2)个(n-2)位数的节点，以此类推，这题的最终目的也就是找一条包含k个节点的路径，也就是整条路径上的节点权重和最大的那条路径，这里的权重定义为:此节点中的关键字与比它多一位的关键字之差的绝对值。也可以把此题想象成一棵树，根节点为n为的整数，叶节点为n-k位的整数，每一层的节点位数相同，但比起父节点少一位，比起孩子节点多一位。代码大致如下：

点击(此处)折叠或打开

  1. int get_result(int& s,int n,int k){
  2.     int rst = 0;
  3.     int i = 0;
  4.     int result = 0;
  5.     int tm = n-(int)(pow(10.0,k-1));
  6.     if(rsult < tm){
  7.         a[i++] = k;
  8.     }
  9. }
  10. int fun(int n,size_t k){
  11.     int m = (int)pow(10.0,(double)(k-1));
  12.     int rst = 0;
  13.     int a = 0;
  14.     int tm = n;
  15.     if(m>n)
  16.         return rst;
  17.     else{
  18.         int j = get_median(n);
  19.         int i = 0;
  20.         int result = 0;
  21.         for(;k>0;--k){
  22.             for(int h=j;--h;h>0){
  23.                 int t = 0;
  24.                 t = tm-(int)(pow(10.0,j-1));
  25.                 if(rsult < t){
  26.                     a = t;
  27.                 }
  28.             }
  29.             tm = a;
  30.             --j;
  31.         }
  32.         rst = tm;
  33.     }
  34.     return rst;
  35. }
上面是一个应用dijkstra算法的简单例子，其实很多求解最有问题都可以转化为搜索问题，并应用dijkstra算法来求解。下面具体说下dijkstra搜索算法：
首先dijkstra算法用于求解有向图切边的权重不为负数的图，对于边为负数的图我们可以用Bellman-Ford算法求解。dijkstra的大致过程是先定义一个空集合C并将源节点加入，然后在整个图的节点结合进行搜索，寻找距集合C“最近”的节点并加入，此处设为v然后对与节点v相连的节点进行松弛，松弛过程大致如下：

点击(此处)折叠或打开

  1. RELAX(u,v,w){
  2.    if(v.d>u.d+w(u,v))
  3.       v.d = u.d+w(u,v);
  4.       v.p = u;
  5. }
注：上述代买来自算法导论
按照上述方法依次进行，直至集合C中的节点数等于图的节点数(图是连通的)。通过上面所述，我们会发现dijkstra算法，和最小生成树的Prim算法以及BFS算法有些相似。
本文来自：http://blog.chinaunix.net/uid-28311809-id-3971392.html
上一篇：Boost Asio之Resolver
下一篇：关于C++中const关键字的一些总结