姜松

摘要：本文讲述了在CAD平台下，利用Auto LISP编程语言，以一个收索图形为例对最短路径问题进行的研究，以及如何提高最短路径的检索速度，快速得出检索结果。

关键词： AutoCAD；Auto LISP；最短路径

Abstract: This paper describes in the CAD platform, using Auto LISP programming language, take a received a cable graphics for example to research on the shortest path problem and how to improve the retrieval speed of the shortest path, and quickly come to retrieve results.Key words: AutoCAD; the Auto the LISP; shortest path

中图分类号：P315.69 文献标识码：A文章编号：2095-2104（2012）

引言

最短路径问题在计算机科学、运筹学、交通工程学、地理信息系统等学科中是一个研究的热点，它是资源分配、线路选择等问题解决的基础，尤其是在诸如地图、车辆调度和路由选择方面有着广泛的应用。基于其具有广泛的应用性，所以本文以一个交通路线的选择为例对其进行了研究，希望能起到抛砖引玉的作用。

1 软件的运行平台及开发语言的简介

AutoCAD是美国Autodesk公司推出的通用计算机绘图软件，它以其强大的绘图功能和良好的开发环境，广泛应用于机械、电子、化工、建筑、测量与勘察等行业。对AutoCAD进行二次开发的手段很多，例如Auto LISP、ADS、ARX、VBA等，本程序使用的是Auto LISP编程语言，它已被嵌入CAD中。Auto LISP具有语法简单、功能强大、易学易用的特点，它的数据类型相当随意，可以组织处理不同长度和结构的数据类型，用户可以按要求和最佳结构设计使用自定义的结构类型数据，而不会感到组织数据结构上的困难。另外，Auto LISP擅长人机交互操作的过程，对用户输入的接受、错误识别、恢复操作等方面的优秀功能，是其它语言难以比及的。

2 程序具体实现

2.1 设计思路

研究最短路径问题，我们不得不提到宽度优先搜索算法（又称广度优先搜索），它是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。……