校园最短路径问题研究

2009年西北民族大学本科生数学建模竞赛承诺书

我们仔细阅读了西北民族大学本科生数学建模竞赛的竞赛规则.

我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。

我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。

我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。

我们参赛选择的题号是（从A/B/C/D中选择一项填写）： B

我们的参赛的论文题目是：校园最短路径问题研究

校园最短路径问题研究

——以西北民族大学榆中校区为例

摘 要: 本文以西北民族大学榆中校区为例，分析了其道路分布的特点，提出了如何选择最短路径的问题，并应用图与网络分析中的Dijskra算法和动态规划中的解决旅行售货员问题的方法，通过建立

合适的数学模型，并适当的应用matlab软件，给出了实际问题中的最短路径和最佳路线，为大家提供参考。建议在学习生活中选择合适的路线。

关键词： Dijskra算法 最短路径 旅行售货员

Abstract

In this paper we use Northwest University for Nationalities YuZhong campus as an example, it analyzes the characteristics of the distribution of the road, and raise a question about how to choose the shortest path, and apply to Graph Theory and Network Analysis with Dijskra algorithm and Dynamic Programming in the Traveling Salesman Problem solving methods, through establish proper mathematical model, and appropriate application of matlab software, present a practical problem the shortest path and the best route, provide the reference for everyone. The suggestion is that we should choose the appropriate route in the study life .

Key words: Dijskra algorithm the shortest path Traveling

Salesman Problem

1、问题的提出

西北民族大学榆中校区是一个占地面积十分庞大的大学校园，由于其中仍有一些主体建筑正在建设过程中，导致校园内道路星罗棋布，错综复杂。而且，交通问题关乎到每一个民大人的出行等日常生活，因此，校园路径问题成为了一个很有必要进行研究的方向。

正由于西北民族大学校园面积广大加上建筑较多，导致校园内的道路错综复杂。基于以上原因，如何在这些道路中选取一条最优路径成为了每个民大人所必须要考虑的交通问题。现在，把该问题大致分为三种情况：

问题一：因为在中午，食堂比较忙碌，有部分同学为了节约时间会选择叫外卖。现在，一个校外餐馆的职工从校门口出发，将外卖送到学校内某一个主要建筑。试求出最短路线。

问题二：在问题一的基础上，进行深一步的研究。试分析求出在校园内任意两点间的最短路径。

问题三：西北民族大学经常会进行学术交流等一系列活动，那么，在参观时，所选的每个点都应该考虑到。试分析应如何选择才使参观人员所走路线最短。

2、模型的假设

2.1模型中选择的道路均为正常道路，一些狭窄、不常有人经过的小路和行人践踏草坪踩出的路不在讨论范围之内。

2.2为使分析问题更加方便，一些实际上不通的道路，如正在修建中的工程所拦住的道路，我们假设它是通的。

3、问题一：模型的建立与求解

3.1问题的描述与分析：因为作为研究的只有校内的道路，所以假设送外卖人员从学校东大门出发，到达学校内的某个建筑楼，这就是最常见的单个最短路径问题。具体研究从学校东大门（节点1）到学生公寓17#楼（节点18）的最短路径。首先，从学校平面图中选取

合适的一部分作为研究。

图1：校园部分平面图

3.2数据的测量和处理

图1的数据

在这里需要解释的是，起始节点可以是终止节点，终止节点也可以是起始节点，即整个网络图是一个无向图。而且，为了研究的方便，在很多的道路口添加了一些节点。

对于各个节点的解释(即它们实际代表的地点)如下： 节点1 ：东大门 节点4 ：主体育馆 节点5 ：篮球馆 节点6 ：四院部候车点 节点7 ：学生公寓1#楼 节点8 ：洗浴中心 节点9 ：学生公寓4#楼 节点10：1、2号食堂 节点11：男生宿舍通往公教3.3模型的求解

3.3.1 Dijkstra算法的算法思想：

在一个图G中求出点s到点t的最短距离。

dij——表示图中两相邻点i与j的距离，若点i与j不相邻，就

楼的路口

节点12：学生公寓7#楼 节点13：学生公寓10#楼 节点15：学生公寓11#楼 节点16：学生公寓14#楼 节点17：数计学院候车点 节点18：学生公寓17#楼 节点19：3、4号食堂

记dij=∞，但dii=0；

Lit——表示从点i到t点的最短距离；

从s点出发，因Lss=0,将此值标记在s点旁的小方框内，表示s点已经标号；

从s点出发，找出与s点相邻的点中距离最小的一个点，设为r，将Lsr=Lss+dsr的值标在R旁边；

重复上述步骤，一直到t点得到标号为止。 3.3.2本题的解法

1)从1点出发，对1标号，讲L11=0标在1旁； 2)同

1

1

点相邻的未标号的点是2和3，有

L1p=midnd1{2

,m}故对点2标号，并将L12=90的值标in{90==L12，

在点2旁；

3)同标号点1和2相邻但未标号的点有3,4和6，有

L1p=

min{L11+d13,L1+d,=min{270,262,4=1L12+d24=L14； 22L4+d12}2

4)重复上述步骤，直到点19被标号为止。 具体步骤如下：

因为我们是求从学校东大门（节点1）到学生公寓17#楼（节点18）的最短路径，所以，从节点1出发：

1. 从节点1出发，对1标号，将L11=0标在1旁；

2. 同节点1相邻但未标号的节点是2和3，有

L1pmind{1

2

d,13}

min{90,L,故对节点270}2标号，将L1290的

值标在节点2旁，并对1,2加粗；

3. 同节点1和2相邻但未标号的节点有6,4和3，有

L1pmin{L12d26,L127L0}12d2,L2d2,4L11d}13min{410,264,4

故对节点4标号，将L14264的值标在节点4旁，并对2,4加粗；

4. 同节点1,2和4相邻但未标号的节点有6,5和3，有

L1pmin{L12d26,L14d4,1d}L故对节点5L113min{410,365,270}

3标号，将L1pmin{L12d26,L14d45,L11d13}min{410,365,270}L13的值标在节点3旁，并对1,3加粗；

5. 同节点1,2,4和3相邻但未标号的节点有6,5和7，有

L1pmin{L12d26,L14d45,L13d37}min{410,365,607}L14d45L

15

,

故对节点5标号，将L15365的值标在节点5旁，并对4,5加粗；

6. 同节点1,2,3,4和5相邻但未标号的节点有6,10,和7，有

L1pmin{L12d26,L15d56,L15d57,L13d37}min{410,485,425,653,607}L12d26L16,

故对节点6标号，将L16410的值标在节点6旁，并对2,6加粗；

7. 同节点1,2,3,4,5和6相邻但未标号的节点有11,10和7，有

L1pmin{L16d611,LLd,3L3600,425,653,607}15d510,155717d}min{

15

L510d

110

,L

故对节点10标号，将L110425的值标在节点10旁，并对5,10加粗；

8. 同节点1,2,3,4,5,6和10相邻但未标号的节点有11,13,9和7，有

L1pmin{L16d161.,10.Lmin{600,500,501,568,653,607}

101.

d10.

13

,L10.

9

d1,L5

57

d,3,13L7dL

11.

d}

L15000.101.d

L

，}故 对节点11标号，将L1.11500的值标在节点11旁，并{1011

对加粗；

9. 同节点1,2,3,4,5,6,10和11相邻但未标号的节点有14,13,9和

L1pmm

i

7

iL1L1

n

，

n

.

.

有

d

{

{

1

LL

6

d

故对节点13标号，将L1.13501的值标在节点13旁，并对{1013}，加粗； 10.

同节点1,2,3,4,5,6,10,11和13相邻但未标号的节点有

和

iL1

7

14,16,12,9

L1pmd3}

m

7

ni

.

，

1

有

,

1

d{n



L0L{

1

1d16d

.

,L

0

L1

故对节点14标号，将L1.14538的值标在节点14旁，并对{13，14}加粗； 11. 点

L1pmL1

}3d

同节点1，2,3,4,5,6,10,11,，13和14相邻但未标号的节

有

17,16,12,9,

iL1nm3

.

和

4L

,6

1

7

d04

，

,.L

1

有

1

{di7

1

0d

1

,.5

.

9

L

n{2L2,dL7

1

故对节点9标号，将L19568的值标在节点9旁，并对{10,9}加粗； 12. 的

L1pmL1

3

同节点1，2,3,4,5,6,10,11,，13,，14和9相邻但未标号节

}d

点

2m

i

有

4

17,16,12,8

L,1{

6

4

和

.

7

7

.

，

d11,

.2

有

L1,.

14

iL1n.{d1

7

d

,1L

,



9

d,

9

L

1

8

n225L7

61d51L37

3,

故对节点16标号，将L1.16573的值标在节点16旁，并对{13,16}加粗；

13. 同节点1，2,3,4,5,6,10,11,，13,，14，9和16相邻但未

17,18,15,12,8

4

.

标号的节点有

L1pmiLn1{.L13d}

3

1

和

6

7，有

11

62

d

4

L1,d1

7

,L

1.

d1,L.d.,11

89

L

19

,d8

1

1

L,5

d

min{622,7646,7L1d3,6L3474,166742,

，故对节点7标号，将L17607的值标在节点7旁，并对{3,7}加粗； 14.

同节点1，2,3,4,5,6,10,11,，13,，14，9，16和7相邻

17,18,15,12

,.1L

1

6

但未标号的节点有

L1pminL1{.1d4

1

和

,16L

.

1.

8，有

81

L,4

.1

d7

d

d2,1.1L19d,9

8

L,

L1d}78min{622,646,71L61,d4L8,61482,68877647

,故对节点8标号，将L18619的值标在节点8旁，并对{7,8}加粗； 15.

同节点1，2,3,4,5,6,10,11,，13,，14，9，16，7和8相

17,18,15

116.

邻但未标号的节点有

L1pminL1{.1d4

1

和

1

.81

12，有

6

L,4.

1

d7

.1

7

1

,L.

d

1

7

1

,6L.d,21.L1

d}

1

716,64L14.,16dL4421}4

,

6

min{622

故对节点17标号，将L1.17=622的值标在节点17旁，并对{14,17}加粗； 16.

同节点1，2,3,4,5,6,10,11,，13,，14，9，16，7，8和

17相邻但未标号的节点有18,15和12，有

L1p=mi1n.{1L7

1

+7d.

18

,L1

.1

+6d

1

,6L.1

8

+d1..

1126

,L+d

+d,

min{697,646,179169,.61424,642}=L

=11

，故对节点12标号，将L1.12=642的值标在节点12旁，并对{9,12}加粗；

17. 同节点1，2,3,4,5,6,10,11,，13,，14，9，16，7，8，

17和12相邻但未标号的节点有18,和15，有

L1p=min1{.1L7=L1.+d16

=L16

.18

+1d7.

18

,L1

.16

+d

16.18

,L

+1d.1

6

,L1

6.15

+d

1.12

}12}=min{697,64

1.18

，故对节点18标号，将L1.18=646的值标在节点18旁，并对{16,18}加粗。 18.

现在，节点1和节点18都已经被标记，那么，可以直接得

出从学校东大门（节点1）到学生公寓17#楼（节点18）的最短路径，为：

124510131618

19.

且最短距离为646米。

此问题的解答过程图如下：

图2：

但是，由于我们能力有限，此问题只给出了具体解法，并未编写程序。

则由此求出从节点1到节点18的最短路径为： 1—>2—>4—>5—>10—>13—>16—>18

4、问题二：模型的建立与求解

4.1问题的描述与分析：

学生的活动是自由的，可以由任意的一点到另外一点。所以，可以做更加深入的研究。即从校园的任意一幢建筑楼到另外一幢建筑楼，所以，考虑一个总体的问题，就是求任意两点间的最短路径。可以选择学校的整个平面图作为参考。

图3：校园平面图

4.2数据的测量和处理

图3的数据

特别注明，起始节点可以是终止节点，终止节点也可以是起始节点，即整个网络图是一个无向图。而且，为了研究的方便，在很多的道路口添加了一些节点。

对于各个节点的解释(它们实际代表的地点)如下： 1.东大门 2.主体育馆

6．经管院路 7．四院部 9．篮球馆 10．食堂 12．图书馆 13．9．10#楼路口 14．10号楼 15．14号楼 16．17号楼 17．数计候车点 19．现教 数计院 20．土木院路口 23．后山足球场 24．武术体操馆 27．化工生科院路口 4.3模型的求解

28．化工生科院29．实验楼30．行政楼31．公教楼33．34．洗浴中心35．36．37．38．食堂39．乘校车点40．41．卡务中心42．医院校43．乒乓球羽毛馆45．北门 1#楼 4号楼 7号楼 11号楼 20号楼

为了求校园内任意两个建筑物之间的最短距离，针对该无向网络图的任意两点之间的最短路径问题，我们仍采用Dijkstra算法进行求解。

在用matlab软件编写Dijkstra算法的算法思想如下：(关于matlab软件的介绍参考附录，若有兴趣，可自行尝试编写程序) Dijkstra算法思想

按路径长度递增次序产生最短路径算法： 把V分成两组：

1S：已求出最短路径的顶点的集合。

2V-S=T：尚未确定最短路径的顶点集合将T中顶点按最短路径递增的次序加入到S中，保证：

1）从源点到S中各顶点的最短路径长度都不大于从V0到T 中任何顶点的最短路径长度。 2）每个顶点对应一个距离值： S中顶点：从V0到此顶点的最短路径长度； T中顶点：从V0到此顶点的只包括S中顶点作中间。 顶点的最短路径长度：

依据：可以证明V0到T中顶点Vk的最短路径，或是从V0到Vk的

直接路径的权值；或是从V0经S中顶点到Vk的路径权值之和。

5、问题三：模型的建立与求解

5.1问题的描述与分析

参观队伍也并不是每个地方都需要去，选取一些有价值的点来做研究。这就与旅行售货员问题十分的相似了。参观队伍要从正门出发，最后回到正门，求出其最短路径。

图4：研究此问题的图

5.2数据的测量和处理

图4的数据

在这里需要解释的是，起始节点可以是终止节点，终止节点也可以是起始节点，即整个网络图是一个无向图。而且，为了研究的方便，在很多的道路口添加了一些节点。

由于本图是从图2中截取的一部分，故对各个节点的实际代表意义不再解释。如有疑问，请参照问题二中的结点解释。

5.3模型的求解

5.3.1旅行售货员问题的算法思想：旅行售货员问题是图论中的一个著名问题，就是在网络N上找一条从v0点出发，经过v1，

v2，……,vn各一次最后返回v0的最短路线和最短路程。先把它看成一

个多阶段决策问题。从v0出发，经过n个阶段，每个阶段的决策是选择下一个点。如果用所在点的位置来表示状态，那么状态与阶段数就不能完全决定集合了，因为走过的点不需要再走，所以决策集合与以前选的决策有关。用(vi,v)表示状态，vi是所处的点，v是还没有经过的点的集合。在状态的(vi,v)决策集合v中，取决策vj∈v,获得的效益是vi到vj的距离dij,转入下一个状态，(vj,v\{vj}),现在用最优化原理来找递推公式。

用fk(vi,v)表示从vi点出发，经过v中的点各一次，最后回到v0点的最短路程，v是一个顶点集合，|v|=k,dij是vi到vj的弧长，则

fk(vi,V)=min{dij+fk-1(vj,V\{vj})},k=1,2nFk(vi,V)=min

vj∈V

f0(vi,φ)=di0 5.3.2本问题的解答 N——阶段数

S——状态量，在某一阶段的状态

fn(s)——当状态量为s时还要n个阶段的最短距离 d(s,vi)——由s->vi的距离

先从最后一个阶段解起，即第0段， 由题意列：

f0(v2,)=f0(v4,)=f0(v5,)=……=f0(v31,)=0 为vi直接到v1的距离i

从1~31且i不取3

f0(v3,)=d31=90 为v3 直接到v1 的距离

第一阶段：

f1(v2,{v3})=d23+f0(v3,)=262 为v2经过v3到v1的距离 f1(v4,{v3})=d43+f0(v3,)=390 为v4经过v3到v1的距离 f1(v8,{v3})=d53+f0(v3,)=410 为v8经过v3到v1的距离

其余的 f1(v2,{v4})=d24=min{vi,vj}=472 则f1(vi,{vj})=min(vi,vj) 为vi经过vj到v1的距离 第二阶段得出：

f2(v2,{v3,v4})=562 为v2经过v3,v4到v1的距离

f30(v1,{v2,,v31})=f2(vi,{vj,vm}) min(vi,vj,vm)为vi经过vj,vm到v1的距离

……

第30阶段得出的结果太长，在此就不一一列举。就举出一个简单的例子来说明：选择图5中的节点3、节点2、节点8、节点9、节点10、节点11，用matlab软件采用上述方法得出要经过每个节点的最短路径为：

3->2->9->10->11->8->3

其最短路径长度为： 1040米。

6、模型的优缺点

6.1优点

大家生活在一个占地面积庞大并经常有各种学术交流的校园中，不可避免的要考虑到交通问题。本文为了解决日常生活中的送饭和最

短路线问题，花了很大的工夫去研究该问题。最终确定用Dijskra算法来解决单源最短路径问题和任意两点之间的最短路径问题，用解决旅行售货员问题的多阶段决策方法来解决参观性问题。为了使数据有很强的真实性和说服力，还在室外进行了多次测量。为了解决实际问题，选择了贴近生活的周边事物进行研究。通过我们研究的成果，大家可以在出行前参照一下图1和程序的运行结果来选择最佳路线。而且，就算以后还有新的建筑楼的建成，本文的方法也是值得借鉴的。

6.2缺点

论文中各点间的距离是由米尺测量得出，与真实的数据存在一定误差。由于能力有限，对于有些问题还无法做到完全用程序来解决。需要大家自己依据合适的方法来解决，这不得不说是一个遗憾。在学习生活中还得依据实际情况来选择合适自己的最优路径。（考虑每条路上的人流量、天气情况等）

参考文献：

《运筹学》第三版 作者：刁在筠 高等教育出版社出版 出版时间：2002年

2009年西北民族大学本科生数学建模竞赛承诺书

我们仔细阅读了西北民族大学本科生数学建模竞赛的竞赛规则.

我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。

我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。

我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。

我们参赛选择的题号是（从A/B/C/D中选择一项填写）： B

我们的参赛的论文题目是：校园最短路径问题研究

校园最短路径问题研究

——以西北民族大学榆中校区为例

摘 要: 本文以西北民族大学榆中校区为例，分析了其道路分布的特点，提出了如何选择最短路径的问题，并应用图与网络分析中的Dijskra算法和动态规划中的解决旅行售货员问题的方法，通过建立

合适的数学模型，并适当的应用matlab软件，给出了实际问题中的最短路径和最佳路线，为大家提供参考。建议在学习生活中选择合适的路线。

关键词： Dijskra算法 最短路径 旅行售货员

Abstract

In this paper we use Northwest University for Nationalities YuZhong campus as an example, it analyzes the characteristics of the distribution of the road, and raise a question about how to choose the shortest path, and apply to Graph Theory and Network Analysis with Dijskra algorithm and Dynamic Programming in the Traveling Salesman Problem solving methods, through establish proper mathematical model, and appropriate application of matlab software, present a practical problem the shortest path and the best route, provide the reference for everyone. The suggestion is that we should choose the appropriate route in the study life .

Key words: Dijskra algorithm the shortest path Traveling

Salesman Problem

1、问题的提出

西北民族大学榆中校区是一个占地面积十分庞大的大学校园，由于其中仍有一些主体建筑正在建设过程中，导致校园内道路星罗棋布，错综复杂。而且，交通问题关乎到每一个民大人的出行等日常生活，因此，校园路径问题成为了一个很有必要进行研究的方向。

正由于西北民族大学校园面积广大加上建筑较多，导致校园内的道路错综复杂。基于以上原因，如何在这些道路中选取一条最优路径成为了每个民大人所必须要考虑的交通问题。现在，把该问题大致分为三种情况：

问题一：因为在中午，食堂比较忙碌，有部分同学为了节约时间会选择叫外卖。现在，一个校外餐馆的职工从校门口出发，将外卖送到学校内某一个主要建筑。试求出最短路线。

问题二：在问题一的基础上，进行深一步的研究。试分析求出在校园内任意两点间的最短路径。

问题三：西北民族大学经常会进行学术交流等一系列活动，那么，在参观时，所选的每个点都应该考虑到。试分析应如何选择才使参观人员所走路线最短。

2、模型的假设

2.1模型中选择的道路均为正常道路，一些狭窄、不常有人经过的小路和行人践踏草坪踩出的路不在讨论范围之内。

2.2为使分析问题更加方便，一些实际上不通的道路，如正在修建中的工程所拦住的道路，我们假设它是通的。

3、问题一：模型的建立与求解

3.1问题的描述与分析：因为作为研究的只有校内的道路，所以假设送外卖人员从学校东大门出发，到达学校内的某个建筑楼，这就是最常见的单个最短路径问题。具体研究从学校东大门（节点1）到学生公寓17#楼（节点18）的最短路径。首先，从学校平面图中选取

合适的一部分作为研究。

图1：校园部分平面图

3.2数据的测量和处理

图1的数据

在这里需要解释的是，起始节点可以是终止节点，终止节点也可以是起始节点，即整个网络图是一个无向图。而且，为了研究的方便，在很多的道路口添加了一些节点。

对于各个节点的解释(即它们实际代表的地点)如下： 节点1 ：东大门 节点4 ：主体育馆 节点5 ：篮球馆 节点6 ：四院部候车点 节点7 ：学生公寓1#楼 节点8 ：洗浴中心 节点9 ：学生公寓4#楼 节点10：1、2号食堂 节点11：男生宿舍通往公教3.3模型的求解

3.3.1 Dijkstra算法的算法思想：

在一个图G中求出点s到点t的最短距离。

dij——表示图中两相邻点i与j的距离，若点i与j不相邻，就

楼的路口

节点12：学生公寓7#楼 节点13：学生公寓10#楼 节点15：学生公寓11#楼 节点16：学生公寓14#楼 节点17：数计学院候车点 节点18：学生公寓17#楼 节点19：3、4号食堂

记dij=∞，但dii=0；

Lit——表示从点i到t点的最短距离；

从s点出发，因Lss=0,将此值标记在s点旁的小方框内，表示s点已经标号；

从s点出发，找出与s点相邻的点中距离最小的一个点，设为r，将Lsr=Lss+dsr的值标在R旁边；

重复上述步骤，一直到t点得到标号为止。 3.3.2本题的解法

1)从1点出发，对1标号，讲L11=0标在1旁； 2)同

1

1

点相邻的未标号的点是2和3，有

L1p=midnd1{2

,m}故对点2标号，并将L12=90的值标in{90==L12，

在点2旁；

3)同标号点1和2相邻但未标号的点有3,4和6，有

L1p=

min{L11+d13,L1+d,=min{270,262,4=1L12+d24=L14； 22L4+d12}2

4)重复上述步骤，直到点19被标号为止。 具体步骤如下：

因为我们是求从学校东大门（节点1）到学生公寓17#楼（节点18）的最短路径，所以，从节点1出发：

1. 从节点1出发，对1标号，将L11=0标在1旁；

2. 同节点1相邻但未标号的节点是2和3，有

L1pmind{1

2

d,13}

min{90,L,故对节点270}2标号，将L1290的

值标在节点2旁，并对1,2加粗；

3. 同节点1和2相邻但未标号的节点有6,4和3，有

L1pmin{L12d26,L127L0}12d2,L2d2,4L11d}13min{410,264,4

故对节点4标号，将L14264的值标在节点4旁，并对2,4加粗；

4. 同节点1,2和4相邻但未标号的节点有6,5和3，有

L1pmin{L12d26,L14d4,1d}L故对节点5L113min{410,365,270}

3标号，将L1pmin{L12d26,L14d45,L11d13}min{410,365,270}L13的值标在节点3旁，并对1,3加粗；

5. 同节点1,2,4和3相邻但未标号的节点有6,5和7，有

L1pmin{L12d26,L14d45,L13d37}min{410,365,607}L14d45L

15

,

故对节点5标号，将L15365的值标在节点5旁，并对4,5加粗；

6. 同节点1,2,3,4和5相邻但未标号的节点有6,10,和7，有

L1pmin{L12d26,L15d56,L15d57,L13d37}min{410,485,425,653,607}L12d26L16,

故对节点6标号，将L16410的值标在节点6旁，并对2,6加粗；

7. 同节点1,2,3,4,5和6相邻但未标号的节点有11,10和7，有

L1pmin{L16d611,LLd,3L3600,425,653,607}15d510,155717d}min{

15

L510d

110

,L

故对节点10标号，将L110425的值标在节点10旁，并对5,10加粗；

8. 同节点1,2,3,4,5,6和10相邻但未标号的节点有11,13,9和7，有

L1pmin{L16d161.,10.Lmin{600,500,501,568,653,607}

101.

d10.

13

,L10.

9

d1,L5

57

d,3,13L7dL

11.

d}

L15000.101.d

L

，}故 对节点11标号，将L1.11500的值标在节点11旁，并{1011

对加粗；

9. 同节点1,2,3,4,5,6,10和11相邻但未标号的节点有14,13,9和

L1pmm

i

7

iL1L1

n

，

n

.

.

有

d

{

{

1

LL

6

d

故对节点13标号，将L1.13501的值标在节点13旁，并对{1013}，加粗； 10.

同节点1,2,3,4,5,6,10,11和13相邻但未标号的节点有

和

iL1

7

14,16,12,9

L1pmd3}

m

7

ni

.

，

1

有

,

1

d{n



L0L{

1

1d16d

.

,L

0

L1

故对节点14标号，将L1.14538的值标在节点14旁，并对{13，14}加粗； 11. 点

L1pmL1

}3d

同节点1，2,3,4,5,6,10,11,，13和14相邻但未标号的节

有

17,16,12,9,

iL1nm3

.

和

4L

,6

1

7

d04

，

,.L

1

有

1

{di7

1

0d

1

,.5

.

9

L

n{2L2,dL7

1

故对节点9标号，将L19568的值标在节点9旁，并对{10,9}加粗； 12. 的

L1pmL1

3

同节点1，2,3,4,5,6,10,11,，13,，14和9相邻但未标号节

}d

点

2m

i

有

4

17,16,12,8

L,1{

6

4

和

.

7

7

.

，

d11,

.2

有

L1,.

14

iL1n.{d1

7

d

,1L

,



9

d,

9

L

1

8

n225L7

61d51L37

3,

故对节点16标号，将L1.16573的值标在节点16旁，并对{13,16}加粗；

13. 同节点1，2,3,4,5,6,10,11,，13,，14，9和16相邻但未

17,18,15,12,8

4

.

标号的节点有

L1pmiLn1{.L13d}

3

1

和

6

7，有

11

62

d

4

L1,d1

7

,L

1.

d1,L.d.,11

89

L

19

,d8

1

1

L,5

d

min{622,7646,7L1d3,6L3474,166742,

，故对节点7标号，将L17607的值标在节点7旁，并对{3,7}加粗； 14.

同节点1，2,3,4,5,6,10,11,，13,，14，9，16和7相邻

17,18,15,12

,.1L

1

6

但未标号的节点有

L1pminL1{.1d4

1

和

,16L

.

1.

8，有

81

L,4

.1

d7

d

d2,1.1L19d,9

8

L,

L1d}78min{622,646,71L61,d4L8,61482,68877647

,故对节点8标号，将L18619的值标在节点8旁，并对{7,8}加粗； 15.

同节点1，2,3,4,5,6,10,11,，13,，14，9，16，7和8相

17,18,15

116.

邻但未标号的节点有

L1pminL1{.1d4

1

和

1

.81

12，有

6

L,4.

1

d7

.1

7

1

,L.

d

1

7

1

,6L.d,21.L1

d}

1

716,64L14.,16dL4421}4

,

6

min{622

故对节点17标号，将L1.17=622的值标在节点17旁，并对{14,17}加粗； 16.

同节点1，2,3,4,5,6,10,11,，13,，14，9，16，7，8和

17相邻但未标号的节点有18,15和12，有

L1p=mi1n.{1L7

1

+7d.

18

,L1

.1

+6d

1

,6L.1

8

+d1..

1126

,L+d

+d,

min{697,646,179169,.61424,642}=L

=11

，故对节点12标号，将L1.12=642的值标在节点12旁，并对{9,12}加粗；

17. 同节点1，2,3,4,5,6,10,11,，13,，14，9，16，7，8，

17和12相邻但未标号的节点有18,和15，有

L1p=min1{.1L7=L1.+d16

=L16

.18

+1d7.

18

,L1

.16

+d

16.18

,L

+1d.1

6

,L1

6.15

+d

1.12

}12}=min{697,64

1.18

，故对节点18标号，将L1.18=646的值标在节点18旁，并对{16,18}加粗。 18.

现在，节点1和节点18都已经被标记，那么，可以直接得

出从学校东大门（节点1）到学生公寓17#楼（节点18）的最短路径，为：

124510131618

19.

且最短距离为646米。

此问题的解答过程图如下：

图2：

但是，由于我们能力有限，此问题只给出了具体解法，并未编写程序。

则由此求出从节点1到节点18的最短路径为： 1—>2—>4—>5—>10—>13—>16—>18

4、问题二：模型的建立与求解

4.1问题的描述与分析：

学生的活动是自由的，可以由任意的一点到另外一点。所以，可以做更加深入的研究。即从校园的任意一幢建筑楼到另外一幢建筑楼，所以，考虑一个总体的问题，就是求任意两点间的最短路径。可以选择学校的整个平面图作为参考。

图3：校园平面图

4.2数据的测量和处理

图3的数据

特别注明，起始节点可以是终止节点，终止节点也可以是起始节点，即整个网络图是一个无向图。而且，为了研究的方便，在很多的道路口添加了一些节点。

对于各个节点的解释(它们实际代表的地点)如下： 1.东大门 2.主体育馆

6．经管院路 7．四院部 9．篮球馆 10．食堂 12．图书馆 13．9．10#楼路口 14．10号楼 15．14号楼 16．17号楼 17．数计候车点 19．现教 数计院 20．土木院路口 23．后山足球场 24．武术体操馆 27．化工生科院路口 4.3模型的求解

28．化工生科院29．实验楼30．行政楼31．公教楼33．34．洗浴中心35．36．37．38．食堂39．乘校车点40．41．卡务中心42．医院校43．乒乓球羽毛馆45．北门 1#楼 4号楼 7号楼 11号楼 20号楼

为了求校园内任意两个建筑物之间的最短距离，针对该无向网络图的任意两点之间的最短路径问题，我们仍采用Dijkstra算法进行求解。

在用matlab软件编写Dijkstra算法的算法思想如下：(关于matlab软件的介绍参考附录，若有兴趣，可自行尝试编写程序) Dijkstra算法思想

按路径长度递增次序产生最短路径算法： 把V分成两组：

1S：已求出最短路径的顶点的集合。

2V-S=T：尚未确定最短路径的顶点集合将T中顶点按最短路径递增的次序加入到S中，保证：

1）从源点到S中各顶点的最短路径长度都不大于从V0到T 中任何顶点的最短路径长度。 2）每个顶点对应一个距离值： S中顶点：从V0到此顶点的最短路径长度； T中顶点：从V0到此顶点的只包括S中顶点作中间。 顶点的最短路径长度：

依据：可以证明V0到T中顶点Vk的最短路径，或是从V0到Vk的

直接路径的权值；或是从V0经S中顶点到Vk的路径权值之和。

5、问题三：模型的建立与求解

5.1问题的描述与分析

参观队伍也并不是每个地方都需要去，选取一些有价值的点来做研究。这就与旅行售货员问题十分的相似了。参观队伍要从正门出发，最后回到正门，求出其最短路径。

图4：研究此问题的图

5.2数据的测量和处理

图4的数据

在这里需要解释的是，起始节点可以是终止节点，终止节点也可以是起始节点，即整个网络图是一个无向图。而且，为了研究的方便，在很多的道路口添加了一些节点。

由于本图是从图2中截取的一部分，故对各个节点的实际代表意义不再解释。如有疑问，请参照问题二中的结点解释。

5.3模型的求解

5.3.1旅行售货员问题的算法思想：旅行售货员问题是图论中的一个著名问题，就是在网络N上找一条从v0点出发，经过v1，

v2，……,vn各一次最后返回v0的最短路线和最短路程。先把它看成一

个多阶段决策问题。从v0出发，经过n个阶段，每个阶段的决策是选择下一个点。如果用所在点的位置来表示状态，那么状态与阶段数就不能完全决定集合了，因为走过的点不需要再走，所以决策集合与以前选的决策有关。用(vi,v)表示状态，vi是所处的点，v是还没有经过的点的集合。在状态的(vi,v)决策集合v中，取决策vj∈v,获得的效益是vi到vj的距离dij,转入下一个状态，(vj,v\{vj}),现在用最优化原理来找递推公式。

用fk(vi,v)表示从vi点出发，经过v中的点各一次，最后回到v0点的最短路程，v是一个顶点集合，|v|=k,dij是vi到vj的弧长，则

fk(vi,V)=min{dij+fk-1(vj,V\{vj})},k=1,2nFk(vi,V)=min

vj∈V

f0(vi,φ)=di0 5.3.2本问题的解答 N——阶段数

S——状态量，在某一阶段的状态

fn(s)——当状态量为s时还要n个阶段的最短距离 d(s,vi)——由s->vi的距离

先从最后一个阶段解起，即第0段， 由题意列：

f0(v2,)=f0(v4,)=f0(v5,)=……=f0(v31,)=0 为vi直接到v1的距离i

从1~31且i不取3

f0(v3,)=d31=90 为v3 直接到v1 的距离

第一阶段：

f1(v2,{v3})=d23+f0(v3,)=262 为v2经过v3到v1的距离 f1(v4,{v3})=d43+f0(v3,)=390 为v4经过v3到v1的距离 f1(v8,{v3})=d53+f0(v3,)=410 为v8经过v3到v1的距离

其余的 f1(v2,{v4})=d24=min{vi,vj}=472 则f1(vi,{vj})=min(vi,vj) 为vi经过vj到v1的距离 第二阶段得出：

f2(v2,{v3,v4})=562 为v2经过v3,v4到v1的距离

f30(v1,{v2,,v31})=f2(vi,{vj,vm}) min(vi,vj,vm)为vi经过vj,vm到v1的距离

……

第30阶段得出的结果太长，在此就不一一列举。就举出一个简单的例子来说明：选择图5中的节点3、节点2、节点8、节点9、节点10、节点11，用matlab软件采用上述方法得出要经过每个节点的最短路径为：

3->2->9->10->11->8->3

其最短路径长度为： 1040米。

6、模型的优缺点

6.1优点

大家生活在一个占地面积庞大并经常有各种学术交流的校园中，不可避免的要考虑到交通问题。本文为了解决日常生活中的送饭和最

短路线问题，花了很大的工夫去研究该问题。最终确定用Dijskra算法来解决单源最短路径问题和任意两点之间的最短路径问题，用解决旅行售货员问题的多阶段决策方法来解决参观性问题。为了使数据有很强的真实性和说服力，还在室外进行了多次测量。为了解决实际问题，选择了贴近生活的周边事物进行研究。通过我们研究的成果，大家可以在出行前参照一下图1和程序的运行结果来选择最佳路线。而且，就算以后还有新的建筑楼的建成，本文的方法也是值得借鉴的。

6.2缺点

论文中各点间的距离是由米尺测量得出，与真实的数据存在一定误差。由于能力有限，对于有些问题还无法做到完全用程序来解决。需要大家自己依据合适的方法来解决，这不得不说是一个遗憾。在学习生活中还得依据实际情况来选择合适自己的最优路径。（考虑每条路上的人流量、天气情况等）

参考文献：

《运筹学》第三版 作者：刁在筠 高等教育出版社出版 出版时间：2002年