陆一峰
上海一中建筑工程有限公司
摘要：解决最短路径问题通常采用图论方法，比如经典最短路径 Dijkstra算法。本文采用一种更简便的树结构解决最短路径问题，在节约综合布线和最经济桥架选择的实际应用中取得良好效果。
关键词：低复杂度最短路径算法;最经济桥架选择算法
1 引言
在大楼强弱电布线中，如果每个终端点至各类机房的布线距离最短，特别是在大面积空间，密集型用电终端布置布线中将会节约一笔非常可观的线缆费用。Dijkstra算法是一种经典的求解最短路径算法，它采用数据结构中图的概念原理，寻找出最佳路径。本文采用一种树的数据结构，相比于Dijkstra算法的图结构具有更低的计算复杂度，特别是在处理大量数据时，用时更少。同时，基于本文最短路径算法上衍生出的最经济桥架选择算法，在选择桥架布置方向和桥架规格大小时具有重要参考价值。
2 最短路径问题描述
给定一个赋权的拓扑图D=(V，A)，V为顶点集，A为边集，记D中每一条弧aij=(vi，vj)上的权为wij(aij)=wij。给定D中一个起点vs和vt终点，设P是D中从vs到vt的一条路，则定义路P的权是P中所有弧的权之和，记为w(P)，即：w(P)=∑wij。又若P1是D图中vs到vt的一条路，且满足w(P1)=min{w(P)}，式中对D的所有从vs到vt的路P取最小，则称P1为从vs到vt的最短路径，w(P1)为从vs到vt的最短距离。
最短路径算法有多种，Dijkstra、Floyd、Kruskal等算法，其中Dijkstra是最常用的求最短路径的算法。Dijkstra算法核心思想就是采用逐节点扩展的方式，确定各节点到起始点的最短距离。Dijkstra算法的具体步骤：
①给vs以P标号，D(vs)=0，其余的各点为T标号（P标号表示节点在B集，T标号表示节点在C集），T(vi)=+∞；
②若vi为刚得到P标号的点，选择T标号点vj，进行修改:D(vj)=min{D(vj),D(vi)+wij}，记录vi与vj关系；(wij为节点i、j支路权值)
③在C集中选择D(vi)最小的节点vi，给vi以P标号重复②直到处理完所有节点；
④搜索完时，所有节点的D值已确定，对应所求终点D值及前后节点关系可找到最短路径。
Dijkstra算法无论采用邻接矩阵或邻接表数据结构，在大样本数据计算中，耗费的时间太长。
3 一种低复杂度最短路径算法
本文将Dijkstra算法以图为基础的数据结构转化为以树为基础的数据结构，将大大降低算法的时间复杂度。
低计算复杂度的最短路径算法原理：
.png)
最短路径长度=Min{=Sum[(a,b)+(b,d)+(d,e)+ (e,z)] ,=Sum[(a,b)+(b,d)+ (d,z) ], ……﹜
备注：Min()求最小值函数
Sum()求和函数
权值(a,b)=4
计算出最短路径长度后，最后回溯输出经过的最短路径点。
4与Dijkstra算法复杂度比较
Dijkstra算法采用邻接矩阵数据结构的时间复杂度是o(n2) ，采用邻接表数据结构的时间复杂度是o(n+e),采用本文算法的时间复杂度是o(n)，可以见o(n) ＜o(n+e)＜o(n2)，在大样本数据计算中节约时间是非常可观的，而且本文算法还可以采用并行程序运行，能进一步节约计算时间。
5最经济桥架选择算法
算法原理：
首先运行各起点至于终点（实际应用中一般认为是机房）的最短路径算法，拾取图1前5个点位至终点Z的运行结果如下：
a→z 最短路径﹛a,c,b,d,e,z﹜
b→z 最短路径﹛b,d,e,z﹜
c→z 最短路径﹛c,b,d,e,z﹜
d→z 最短路径﹛d,e,z﹜
e→z 最短路径﹛e,z﹜
统计以上各路径重复次数：
.png)
图2：某地下停车场
.png)
7 结束语
本文采用在Excel的VBA中，使用优化的最短路径算法和树数据结构解决最短路径问题，在实际应用中，可以在CAD软件中加入插件程序，由手工输入权值改成自动拾取权值，将大大简化实操性，使本方法更能推广应用。
参考文献：
[1]Excel求解最短路径问题 广东女子职业技术学院 金晓龙
[2]《数据结构》 主编 苏仕华 2012版