最短路径算法 [基于Dijkstra最短路径算法的教育装备更新问题]

基于Dijkstra最短路径算法的教育装备更新问题

教育装备必须经历一个管理知识量化的过程，才能从经 验管理向科学管理过渡，使得管理工作成为可预测、可测量、 可重复、可控制的科学管理过程[1]。为此，就必须把管理 学、运筹学等理论和方法引入教育装备管理中来，以科学方 法解决实际问题。目前我国的经济发展水平和社会发展阶段 共同决定了下发到各个学校的教育经费的有限性，在满足日 常的教育需求和科研工作的前提下，学校要考虑教育装备的 更新成本以及继续使用旧装备的维修费用等问题，尽可能地 压缩教育装备的更新费用是教育装备管理工作中面临的难 题。本文以解决教育装备更新问题为切入点，应用基于 Dijkstra的最短路径算法实现其总费用最小化的求解，为教 育装备资源分配工作提供科学依据。

1 算法的基本概念图论的起源可以追溯到瑞士数学家（E.Euler）在1736 年发表的一篇解决“哥尼斯堡七桥问题”的论文。在自然界 和人类社会中，大量的事物以及事物之间的关系，常可以用 图来描述[2]。随着现代生产和科学技术的迅猛发展，特别 是计算机的出现和互联网的普及，使图论方法得以快速扩展， 图论已成为运筹学中引人注目的重要分支，渗透到物理学、 化学、电工学、管理学、控制论、信息论等诸多学科[3-4]。

最短路径问题是图论中应用最广泛的问题之一。许多实 际问题求最优解可以使用这个模型，如设备更新、管道铺设、 选址布局等。所谓最短路径是指在一个连通图中，求从某一 个指定结点（起始点）到另一个指定结点（终点）的距离最 短的路径，即：寻求赋权图中任意两点之间的最短路径。这 里的最短路径只是图中边权数的代名词，在解决实际问题时， 它可以是时间、费用等其他不同含义的量[5]。

Dijkstra算法是解决最短路径问题的常用算法之一，适 用于所有权wij≥0情况下求指定两点间的最短路径，目前已 经被广泛应用。在这里可以把教育装备更新问题抽象为赋权 有向图，利用Dijkstra算法进行求解，从而得到某段时间内 总费用最少的路径，为教育装备的更新提供最优化方法。图的相关概念 1）图（Graph），即偶对（V，E），记作G（V，E）。

其中，V是顶点（Vertex）的集合，E是边的集合。

2）有向图（Digraph），即有序偶对（V，E），记作D= （V，A）。其中，V是顶点（Vertex）的集合，A是弧的集合。

换言之，有向图就是所有边都具有一定方向的图。

3）赋权图（Weighted graph），即在图G（V，E）中， 每一条边（vi，vj）均有一个数wij与之对应，数wij即为边 （vi，vj）的权值。

4）连通图（Connected graph）：设vi和vj为图G中的 两个点，若存在从点vi到点vj的链，则称vi和vj是连通 的；
若图G中的任意一对顶点均连通，则图G被称为连通 图。

Dijkstra算法的基本思想 Dijkstra算法的基本思路是 把图中的全部顶点分为两组，令V表示已标记最短路径的顶 点集合，其余未标记最短路径的顶点集合为V；
初始状态时， 集合V中只含有起始点s，V中含有除起始点s之外的其余各顶点，此时各顶点的当前最短路径为起始点到该节点的弧上的 权值；
然后不断地从集合V中选取到顶点集V中各顶点的路径 长度最短的顶点u加入到集合V中，集合V中每加入一个新的 顶点u，都要分别修改已标记集合V和未标记集合V中的顶点。

集合V中各顶点新的最短路径长度值为原来的最短路径长度 值加上u到该顶点的路径长度值中的较小值。重复此过程， 直到集合V包含图中所有顶点（即所有顶点都被标记）为止。

定义dij是图中顶点i和j之间的距离，即：
给定赋权有向图D=（V，A），采用Dijkstra算法求从起 始点s到终点t的最短路径的具体步骤如下。

1）从起始点s出发，每个节点都进行标记，记作Lij；

其中Lij是从节点i到节点j的最短路径。Lss=0（从顶点到其 本身的最短路径是零路——没有弧的路[6]，其长度为0）， 将点s标记为“0”，表示点s已被标记。令s∈V，其余各点 均属于V。

2）从起始点s出发，找到与点s相邻且距离最短的点i， 将Lsi=Lss+Lsi的值作为节点i的标记，表示节点i已被标记。

令（s，i）∈V，其余各点均属于V。3）找出所有与已标记点相邻的未标记的点（即广度优 先搜索），若Lsj=min{Lss+dsj，Lsi+dij}，则给点j标记。

令（s，i，j）∈V，其余各点均属于V。

4）重复第三步，直到终点t被标记（即集合V为空）为 止，算法结束。

重复操作以上步骤共n-1次，由此求得从s到图上其余各 顶点的最短路径[7]。

2 实例应用 建立数学模型 本文用一个简单的数学模型来说明教育 装备更新问题。假设某学校的电教实验室使用一种电教装备， 每年的年初，管理员都要决定是继续使用旧装备，还是购买 新装备。如果继续使用旧装备，就要支付一定的维修费用， 随着装备的老化，维修费也会随之上升（如表1所示）；
如 果购置新装备，就要付购置费和相应较少的维修费（如表2 所示）；
如果购置新装备或不想继续维修，打算把旧装备卖 掉折旧，就可以获得部分折旧费，随着装备的老化破碎，折 旧费会随之减少（如表2所示）。试制订一个4年的电教装备 更新计划，使总支出最少。

显然，可供选择的装备更新方案是很多的，但是每种方案花费的总费用不同。

如每年都购买一台新的装备（即使用一年就更新），则 其购置费是27+28+29+30=114（百元）；
而每年支付的维修 费用是5（百元），4年维修费合计是20（百元），于是4年 总的支付费用是114+20=134（百元）；
再减去4年中每年的 装备折旧费24+20+17+14=75（百元），最后为59（百元）。

又如决定第一年购买的装备一直使用到第四年年底，则 4年支付费用总和为第1年的装备购置费加上四年中每年的 维修费，合计为27+5+7+9+11=59（百元），再去掉第四年年 底的装备折旧费14（百元），为44（百元）。

如何制订方案，使得总支付费用最小呢？可以把这个问 题转化为赋权有向图（如图1所示），然后转为求解最短路 径问题。

令vi表示第i年年初购进一台新装备（i=1，2，3，4，5）， v5表示第四年年底。

（vi，vj）表示第i年购进的新装备一直使用到第j年年 初（即第j-1年年底）（j=2，3，4，5）。

wij表示弧（vi，vj）所赋的权值，即第i年购置的装备 的费用加上从第i年使用到第j年年初（即第j-1年年底）的 维修费，再去除相应折旧费的最终结果。

每条弧的权值可按照已知资料（如上给出的两张表）计 算出来，结果如表3所示。如（v1，v3）是第1年年初购进装 备（支付购置费27），一直使用到第2年年底（支付维修费5+7=12），如果第3年年初卖掉折旧（可得折旧费20），故 （v1，v3）上的权值为19。

根据得出的每条边的权值，进而将装备更新问题转化为 赋权连通图，如图2所示。这样制订一个最优的装备更新计 划的问题，就等价于寻求从v1到v5的最短路径问题。

Dijkstra算法的实现 用Dijkstra算法求图2中从v1到 v5的最短路径，此算法结果就对应着总花费最低的装备更新 计划。

1）从点v1出发，对其标“0”。令v1∈V，其余各点均 属于V。

2）与点v1相邻的未标号点有v2、v3、v4和v5四个点， 由于min{0+8，0+19，0+31，0+45}=8，故v2点标号为“8”。

令（v1，v2）∈V，其余各点均属于V。

3）与点v1和点v2相邻的未标号点有v3、v4和v5三个点， 由于min{v1：0+19，0+31，0+45}=19，min{v2：8+13， 8+23， 8+35}=21，取min{19，21}=19，故v3点标号为“19”。

令（v1，v2，v3）∈V，其余各点均属于V。

4）与点v1、点v2和点v3相邻的未标号点有v4和v5两 个点，由于min{v1：0+31，0+45}=31，min{v2：8+23， 8+35}= 31，min{v3：19+17，19+23，19+27}=36，取min{31， 31，36}=31，故v4点标号为“31”。令（v1，v2，v3，v4） ∈V， 其余各点均属于V。

5）与点v1、点v2、点v3和点v4相邻的未标号点仅有v5 一个点了，由于min{v1：0+45}=45，min{v2：8+35}=43， min{v3：19+27}=46，min{v4：31+21}=52，取min{45，43， 46，52}=43，故v5点标号为“43”。此时所有顶点均得 到标号，算法结束。

6）逆推可得到顶点v1到终点v5的最短路径：v1→v2 →v5，最短路径长为43。

因此，总费用最少的电教装备更新方案为：第一年购买 电教装备，使用1年；
第二年年初购买新的电教装备，使用3 年，直至第四年年底，总费用最少是43（百元）。

3 结语 教育装备更新问题是学校在教育装备管理过程中常遇 到的问题，在有限的教育经费下，何时更新装备才能保证教 育经费花费最低，是学校要考虑的重要因素。因此，学校各 院系的教育装备管理者需要运用科学的方法去解决装备更 新的实际问题。Dijkstra算法是单源最短路径的代表性算法， 可以求出其中任一点到其余各点的最短路径，能得出最短路 径的最优解。但是它遍历计算的节点很多，所以效率低。

本文应用Dijkstra算法于装备更新问题，高科技含量的 教育装备更新较快，以年为节点，节点数目不会很多，可以很好地运用Dijkstra算法，通过不断地迭代做出在当前看来 最好的选择，最终找到问题的最优的解决方案。

参考文献 [1]艾伦，姚玉琴，等.教育装备从经验管理走向科学管 理[J].中国教育技术装备，2009（32）：17. [2]胡运权，郭耀煌.运筹学教程[M].2版.北京：清华大 学出版社，2003：252-253. [3]辛宇.基于运筹学图论的物流网络优化研究[J].中 国外资，2011（6）：125-127. [4]蒋智凯.浅谈运筹学教学[J].重庆科技学院学报：社 会科学版，2010（24）：176-177. [5]李慧.教育装备运筹规划[M].北京：北京大学出版社， 2010：100-116. [6]乐阳，龚健雅.Dijkstra最短路径算法的一种高效率 实现[J].武汉测绘科技大学学报，1999（3）：209-212. [7]许永昌，王甲琛.基于最短路径问题在企业设备更新 中的应用[J].山东英才学院学报，2006（4）：64-65.中国教育技术装备