◆曹莹莹　李慧

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

◆曹莹莹李慧

随着教育水平的不断提升，教育领域教育装备的投入步伐大大加快，设备的更新换代越发频繁。为了最大限度发挥教育装备的功能，保障优质教学，学校每年都要对教育装备进行更新与维护且使总费用最小化。首先建立教育装备更新数学模型，阐明如何更新教学中的设备使总费用最小化，并采用Dijkstra最短路径算法实现教育装备的更新。

教育装备更新；最短路径；Dijkstra算法

10.3969/j.issn.1671-489X.2016.16.001

随着计算机技术和教育信息化的发展，具有先进技术含量的教育装备在教育教学中得到广泛应用，教育装备的分配、管理、购置和维修等问题也随之变得更为复杂。先进的教育装备不仅能为学校提供良好的教学环境和丰富的教学资源，还能锻炼学生的实践能力和创新思维。因此，在当前的教育教学中，先进的教育装备已逐渐成为教学过程中不可或缺的重要条件。

教育装备必须经历一个管理知识量化的过程，才能从经验管理向科学管理过渡，使得管理工作成为可预测、可测量、可重复、可控制的科学管理过程［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中只含有起始点s，中含有除起始点s之外的其余各顶点，此时各顶点的当前最短路径为起始点到该节点的弧上的权值；然后不断地从集合中选取到顶点集V中各顶点的路径长度最短的顶点u加入到集合V中，集合V中每加入一个新的顶点u，都要分别修改已标记集合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，其余各点均属于。

2）从起始点s出发，找到与点s相邻且距离最短的点i，将Lsi=Lss+Lsi的值作为节点i的标记，表示节点i已被标记。令（s，i）∈V，其余各点均属于。

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

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

2　实例应用

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

表1　4年内装备维修费

表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　装备更新问题的有向图

表3　所有弧的权值wij单位（百元）

图2　装备更新问题的赋权连通图

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

2）与点v1相邻的未标号点有v2、v3、v4和v5四个点，由于min｛0+8，0+19，0+31，0+45｝=8，故v2点标号为“8”。令（v1，v2）∈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，其余各点均属于。

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，其余各点均属于。

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.

图2

Educational Equipment Update Problem based on Dijkstra's Shortest Path Algorithm

//CAO Yingying， LI Hui

With the rising levels of education， in the fi eld of education greatly accelerate the pace of investment in educational equipment，more frequent replacement of equipment. In order to maximize the function of educational equipment to ensure the quality of teaching，the schools update and maintain educational equipment every year to minimize the total cost. Firstly， the article builds the mathematical models of educational equipment update and illustrates how to update educational device， minimizing the total cost. And， the article uses the Dijkstra's shortest path algorithm to realize the educational equipment update.

educational equipment update； the shortest path； Dijkstra algorithm

G650

A

1671-489X（2016）16-0001-03

作者：曹莹莹，首都师范大学教育技术系，研究方向为教育传播理论与技术；李慧，博士，首都师范大学教育技术系副教授、硕士生导师，研究方向为教育装备、教育技术学（100048）。