32个重要算法之Dijkstra算法

我们首先给出一个用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位的整数，每一层的节点位数相同，但比起父节点少一位，比起孩子节点多一位。代码大致如下：

int get_result(int& s,int n,int k){
    int rst = 0;
    int i = 0;
    int result = 0;
    int tm = n-(int)(pow(10.0,k-1));
    if(rsult < tm){
        a[i++] = k;
    }
}
int fun(int n,size_t k){
    int m = (int)pow(10.0,(double)(k-1));
    int rst = 0;
    int a = 0;
    int tm = n;
    if(m>n)
        return rst;
    else{
        int j = get_median(n);
        int i = 0;
        int result = 0;
        for(;k>0;--k){
            for(int h=j;--h;h>0){
                int t = 0;
                t = tm-(int)(pow(10.0,j-1));
                if(rsult < t){
                    a = t;
                }
            }
            tm = a;
            --j;
        }
        rst = tm;
    }
    return rst;
}

上面是一个应用dijkstra算法的简单例子，其实很多求解最有问题都可以转化为搜索问题，并应用dijkstra算法来求解。下面具体说下dijkstra搜索算法：
首先dijkstra算法用于求解有向图切边的权重不为负数的图，对于边为负数的图我们可以用Bellman-Ford算法求解。dijkstra的大致过程是先定义一个空集合C并将源节点加入，然后在整个图的节点结合进行搜索，寻找距集合C“最近”的节点并加入，此处设为v然后对与节点v相连的节点进行松弛，松弛过程大致如下：

RELAX(u,v,w){
   if(v.d>u.d+w(u,v))
      v.d = u.d+w(u,v);
      v.p = u;
}

注：上述代买来自算法导论
按照上述方法依次进行，直至集合C中的节点数等于图的节点数(图是连通的)。通过上面所述，我们会发现dijkstra算法，和最小生成树的Prim算法以及BFS算法有些相似。
本文来自：http://blog.chinaunix.net/uid-28311809-id-3971392.html