excel 求解最短路径问题

《excel 求解最短路径问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Excel求解最短路径问题金晓龙（广东女子职业技术学院艺信系,广东广州511450）摘要：许多实际应用问题都与最短路径相关，解决最短路径问题通常采用图论与计算机技术结合的方法，本文使用Excel的工作表和自定义宏函数，采用Dijkstra算法和链表动态数据结构解决最短路径问题，并在Excel的VBA环境编程运行。关键词：Excel最短路径链表Dijkstra算法中图分类号：TP311ExcelSolutionofShortestPathProblemJinXiaolong（GuangdongWomen’sPolytechnicCollege,Arta

2、ndInformationDepartment,Guangzhou511450,China）Abstract：Manypracticalapplicationproblemsarerelatedtotheshortestpathproblem.Themethodcombinedgraphtheorywithcomputertechnologyisusuallyadoptedtosolvetheshortestpathproblem.ThisarticledescribeshowtosolvetheshortestpathproblembyusingE

3、xcelworksheetandcustommacrofunctions,Dijkstraalgorithmandlinkedlistofdynamicdatastructure.Finally,allisprovedbyprogrammingandrunninginExcelVBA.Keywords：Excel；shortestpasth；dynamicarray；Dijkstraalgorithm1引言在实际应用中，许多问题都与最短路径有关，如：物流路径、交通导航、网络路由、电力传输、综合布线等，而且最短路径还可抽象为许多其它的实际问题，如：最小

4、费用、最短时间、最小负载、最少人员等，解决最短路径问题通常采用图论与计算机技术结合的方法。图论是数学的一个分支，它以图为研究对象，研究顶点和边组成的图形的数学理论和方法。Dijkstra算法是一种经典的求最短路径算法，它采用标号法反复扫描网络的节点，寻找出最佳路径。本文采用Dijkstra算法与链表数据结构相结合，在Excel的VBA中编程实现最短路径搜索。Excel是应用广泛的电子表格软件，在其自带的VBA环境里而非专门的编程环境里解决最短路径问题，更具有一定的实际意义。由于在VBA中不能显式使用指针，采用类实现链表数据结构。2最短路径问题给定一个

5、赋权的拓扑图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的最短距离。3最短路径算法最短路径算法有多种，Dijkstra、Floyd、Kruskal等算法，其中Dijkstra是最常用

6、的求最短路径的算法。Dijkstra算法核心思想就是采用逐节点扩展的方式，确定各节点到起始点的最短距离。采用标号法搜索各顶点，标号的目的就是区分该顶点是否已处理过。将顶点分为两个顶点集，第一个为已处理顶点集B，第二个为未处理顶点集C，开始时B中只包括起始点vs，C中包括除起始点外的所有网络节点。确定各顶点vi的D(vi)值，D(vi)值为已探索到vi到起始点vs的最小值，随着搜索的不断进行，D(vi)会发生变化。搜索开始时，D(vs)=0，与起始点相连的D(vi)为支路权值，不与起始点相连的D(vi)为+∞，然后，从C中选一个D(vi)最小的节点，修

7、改与之相连的各节点的D(vi)值，将该节点从C中移到B中，记录下被修改节点的前一节点信息，重复前面过程，直到所有的顶点均搜索。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值已确定，对应所

8、求终点D值及前后节点关系可找到最短路径。4路径图描述及链表结构求图1中节点间的最短路径。5图1带权无向图10