Dantjig标号算法的实现

        说明：t(ai )表示从a1 (起始点)到ai 的最小开销，Ai 表示第i次寻路后已经标记的点的集合，其中共有i个元素，且对1<=j<=i已知t(aj )。对每一个Ai 中的aj ，其临近点的集合为N(aj )。w(aj ak )表示aj 到ak 的权。Ti 表示第i次寻路的最短路径集合。

算法的步骤如下：

1. 从a1 点出发，则t(a1 )=0,A1 ={a1 },T1 ={空集};
2. 若已经得到Ai ={a1 ,a2 , ... ,ai }且对其中的每一个aj 都可以在Bji ={N(aj )-Ai }中找到一点bji 使得aj 到bji 的距离比到其他未标记临近点的距离都短，即w(aj bji )=min(aj bki ) {k!=j, 1<=k<=i}。也就是说对已经标记的每一个点都有一个未标记的邻接点集Bji ，从中都可以找到该点可以到达的下一个最小距离点，所有已标记点的最小距离邻接点可以构成集合Bj；
3. 从Bj中找到一个与起点距离最短的点进行标记，并将之作为下一个起点ai+1 ;
4. 如果ai+1 就是目标点，则停止；否则转到第二步。

        事实上，这个算法可以通过图转化为树的方式来说明，其中最为关键的变量为ai 、Ai 、Bi 、ti 、Ti ，其中Bi 是二维的，对于Ai 中的每一个aj 都有一个集合，但在程序实现时只需要存储每个aj 点的最小距离临近点就行了。在已经形成的树做进一步的扩展时，每次的距离增加量都是最小的。通过这种“贪心”扩展的方式，搜索过程就可以达到择优效果。

        程序中最难实现的就是在未标记的临近点集内找最小开销的路径，所以在这里作简要的分析。整个图用G[MAX][MAX]来存储权值关系，其中G[i][j]表示从ai ->aj 所需要的开销、标记的点用A[MAX]存储、未标记的邻接点集用B[MAX]来存储、到每个已标记点的开销用t[MAX]来存储、路径用T[MAX][2]来存储数值i、j表示从ai ->aj 是一条可选的捷径。则选择的过程可以表述为对已标记的点数组A[MAX]中的每个元素A[i]，从G[A[i]][...]中选出未在A[...]中出现过的最小值G[A[i]][k]，并将其列标号k存储到B[i]中作为这次扩展的可选点。最后只需要从t[i]+w(A[i] B[i])中选出最小路径即可。

 

下面是实现代码。其中默认起点标号为1，终点标号为num。HEAD表示某条路径的头，TAIL表示其尾。

---

/*

* blood.c

*

* Created on: Mar 22, 2010

* Author: lzp

*/

#include <stdio.h>

#include <string.h>

 

#define HEAD 0

#define TAIL   1

 

#define CNT_A 0

#define CNT_B 1

#define CNT_T 2

#define CNT_N 3

 

#define NUM 10

#define MAX 100

 

static int num = 8; // number of points

static int A[NUM] = { 0 };

static int B[NUM] = { 0 };

static int t[NUM] = { 0 };

static int C[CNT_N] = { 0 };

static int T[NUM][2] = { {0} };

static int G[NUM][NUM] = {

{0,2,8,1,0,0,0,0},

{2,0,6,0,1,0,0,0},

{8,6,0,7,4,2,2,0},

{1,0,7,0,0,0,9,0},

{0,1,4,0,0,3,0,9},

{0,0,2,0,3,0,4,6},

{0,0,2,9,0,4,0,2},

{0,0,0,0,9,6,2,0}

};

 

上面的图G是由下面的边赋权图所得

 

int main(void)

{

int i, j, k, min, flag;

// init A & t & T

C[CNT_A] = 1;

for(i=1;i<NUM;++i){

A[i] = -1;

t[i] = MAX;

T[i][0] = -1;

T[i][1] = -1;

}

 

while(A[C[CNT_A]-1]!=num-1){

// 构造B数组

C[CNT_B] = 0;

for(i=0;i<C[CNT_A];++i){

min = MAX;

B[i] = -1;

for(j=0;j<num;++j){

if( (0<G[A[i]][j]) && (G[A[i]][j]<min) ){

flag = 0; // 判断是否在A中出现过

for(k=0;k<C[CNT_A];++k){

if(A[k]==j){

flag = 1;

break;

}

}

if(!flag){

min = G[A[i]][j];

B[i] = j; // 如果没有出现过，则存入B，否则B[i]=-1；

}

}

}

C[CNT_B]++;

}

// 计算最小邻接点，并选择与起点距离最小的点

min = MAX;

for(i=0;i<C[CNT_A];++i){

if(B[i]==-1)

continue;

if(i==0)

flag = G[0][B[0]];

else

flag = t[A[i]] + G[A[i]][B[i]];

if(flag<t[B[i]]) // 只有更小的值才更新

t[B[i]] = flag;

if(t[B[i]]<min){ // 如果是最小距离，则扩展A数组和路径T

min = t[B[i]];

A[C[CNT_A]] = B[i];

T[C[CNT_T]][HEAD] = A[i];

T[C[CNT_T]][TAIL] = B[i];

}

}

C[CNT_A]++;

C[CNT_T]++;

}

// 找路&打印路径

i = C[CNT_T]-1;

printf("%d < %d/n",T[i][TAIL],T[i][HEAD]);

while(T[i][HEAD]!=0){

for(j=i-1;j>=0;j--)

if(T[j][TAIL]==T[i][HEAD]){

i = j;

printf("%d < %d/n",T[i][TAIL],T[i][HEAD]);

break;

}

}

// cost

printf("min %d/n",t[num-1]);

return 0;

}

 

 

数组变量与上面的说明几乎是一致的，只是多了一个t[]数组，用来记录到达已标号点的最小开销。测试结果：

7 < 6

6 < 2

2 < 4

4 < 1

1 < 0

min 11