Floyd算法在一类实际问题中的应用

摘要:最短路径问题在图中是最吸引大家眼球的问题,既是图中的重点也是难点。该文分析了Floyd算法的基本思想,并以一个实际问题为例,论述了其在VC++中的具体实现。

关键词:Floyd算法;VC++;应用

中图分类号:TP311文献标识码:A文章编号:1009-3044(2010)22-6227-02

Application of Floyd Algorithm in a Class of Practical Problems

WEI Lin-jing1,YUE Jian-bin2

(1.Information Science and Technology College, Gansu Agricultural University, Lanzhou 730070, China; 2.Lanzhou City College, Lanzhou 730070, China)

Abstract: Shortest path problem is the most attractive problem in the graph theory. It's not only of great priority, but also a difficult. This paper analyzes the basic idea of floyd algorithm,and discusses the realization in VC++ by a practical problem.

Key words: floyd algorithm; VC++; application

最短路作为图与网络技术研究中的一个经典问题一直在工程规划、地理信息系统、通信和军事运筹学等领域有着十分广泛的应用。顶点对之间的最短路径是指:对于给定的有向网G=(V,E),要对G中任意一对顶点有序对V、W(V≠W),找出V到W的最短距离和W到V的最短距离。

目前,关于最短路问题的研究已有较多结果,传统的最短路算法主要有 Floyd算法[1]和Dijkstra[2]算法等。其中,Dijkstra算法求解任意顶点对之间最短距离的方法是:轮流以每一个顶点为源点,重复执行算法n次,即可求得每一对顶点之间的最短路径,总的时间复杂度为O(n3)。

Floyd提出了另外一个求图中任意两顶点之间最短路径的算法,虽然其时间复杂度也是 O(n3),但其算法的形式更简单,易于理解和编程。

1弗洛伊德(Floyd)算法的基本思想

Floyd算法是通过权矩阵计算来实现的一种方法,其主要思想是从代表任意两个节点vi到vj距离的带权邻接矩阵 D(0)开始,首先计算D(1),即计算vi到vj经过一次经转的所有可能路径,经过比较后选出最短路,代替D(0)中对应的路径,迭代列出距离矩阵D(1),D(1)中各元素表示通过一次迭代后网络中任意两点间最短路,也即网络中任意两点之间直接到达或只经过一个中间点时的最短路。在此基础上依次计算D(2) ,D(3) ,…,D(k),D(k)中对应的元素表示任意两点间不经过中间点或最多允许经过2k-1个中间点时的最短路。当D(k+1) =D(k)时,表明得到的带权邻接矩阵D(k)就反映了所有顶点对之间的最短距离信息,,成为最短距离矩阵。其算法如下:

第一步,作初始距离矩阵D(0)=(dij(0)),其中:

,其中(i,j=1,2,…,n);

第二步,构造迭代矩阵D(k)=(dij(k)),其中:

;

第三步,若D(k+1)=D(k),迭代终止,否则,返回第二步。

2 问题的提出及求解

设计一个能够计算某城市任意两个院校间最短路距的查询器,院校间交通示意图见图1。要求系统应具备较好的容错与自动计算等功能。两个院校间最短路距是指从一个院校校门到另一个院校校门间的最短里程(单位:千米)。

在具体求解过程中,可以把一个学校所在位置作为一个始点,其他任何学校所处的位置都可能成为终点,即终点是任意的。由于Floyd算法是比较成熟的求非负权网络最短路问题的算法,且是一种多项式算法。在实现Floyd算法的过程中,核心步骤就是从未标记的点中选择一个权值最小的弧段,这是一个循环比较的过程。

利用VC++来求解本问题的过程如下。在VC++中运行程序, 为了避免∞在计算机中无法计算的问题,可以把∞改为100来计算(相对其他的数据来说,是比较大的),这样改动后,并不影响程序运行后所得到结果的正确性。

1) 初始化邻接矩阵和路径矩阵

#define N 20

#define INF 100

float cost[N][N];

int path[N][N];

float A[N][N];

int i,j,k;

for(i=0;i

for(j=0;j

{if(i==j)

cost[i][j]=0;

else

cost[i][j]=INF;

}

cost[0][1]=0.5; cost[1][0]=0.5;cost[1][10]=0.3;cost[2][12]=1.5;cost[2][10]=2.2;

cost[3][18]=1.1; cost[3][16]=0.1;cost[4][16]=0.3;cost[4][15]=0.1;cost[5][15]=0.6;

cost[6][15]=0.3; cost[6][7]=1.3;cost[7][6]=1.3;cost[7][8]=1.0;cost[8][7]=1.0;

cost[8][14]=0.2; cost[9][15]=0.3;cost[9][14]=0.1;cost[10][18]=2.6;cost[10][1]=0.3;

cost[10][11]=1.7 ; cost[10][2]=2.2;cost[11][10]=1.7;cost[11][19]=0.7;cost[11][12]=0.5;

cost[12][13]=0.8 ; cost[12][2]=1.5;cost[13][12]=0.8;cost[13][14]=1.1;cost[13][17]=0.5;

cost[14][13]=1.1; cost[14][8]=0.2;cost[14][17]=0.4;cost[14][9]=0.1;cost[15][5]=0.6;

cost[15][6]=0.3; cost[15][4]=0.1;cost[15][9]=0.3;cost[16][3]=0.1;cost[16][4]=0.3;

cost[16][17]=0.4; cost[17][16]=0.4;cost[17][14]=0.4;cost[17][19]=1.2;cost[17][13]=0.5;

cost[18][3]=1.1; cost[18][10]=2.6;cost[18][19]=0.4;cost[19][18]=0.4;cost[19][11]=0.7;

cost[19][17]=1.2;

for(i=0;i

for(j=0;j

A[i][j]=cost[i][j];

if(cost[i][j]

path[i][j]=i;//初始化路径矩阵,原来有路

else

path[i][j]=-1;//原来没有路

}

2) Floyd算法核心代码

for(k=0;k

for(i=0;i

for(j=0;j

if(A[i][j]>(A[i][k]+A[k][j])){

A[i][j]=A[i][k]+A[k][j];

path[i][j]=k;//表示从i到j,要经过k节点

}

3) 系统运行界面

如图2所示。

3 结论

在实际中最短路径的选取需要考虑多种因素,而这些因素往往又是模糊的。如何综合利用这些因素是交通线路选取所面临的一个关键性问题。本文所提出的方法的优点有:1) 它考虑了影响最短路径选择的多种模糊因素,使得最短路径的选取更加客观;2) 它可以动态的计算最短路径,而且计算速度比较快。实践表明,该方法可以有效的、快速的计算出任意两个学校间的最短路径,具有一定的理论价值和很好的应用价值。

参考文献:

[1] 程理民,吴江,张玉林.运筹学模型与方法教程[M].北京:清华大学出版社,2000.

[2] 严蔚敏,吴伟民.数据结构(C 语言版)[M].北京:清华大学出版社,2008.

[3] 周益民,孙世新,田玲.一种实用的所有点对之间最短路径并行算法[J].计算机应用,2005(12):64.