最短路径问题-数学建模比赛

A4A5,A5A6,A6A7,A6A8,A5A9,A8A9，A7A8,A7A11 的集合

G=（V，E）表示带权邻接图，即表（1）汇总excel表格正是此带权邻接矩阵。

根据迪杰斯特拉算法（Dijkstra算法）在全局选取一点作为中心，向外层层扩展，直到扩展到终点为止的思想建立模型求解第二问。

在全局中选取一点X作为中心（即大白此时的位置），根据带权邻接矩阵表（1），所示向外层层扩展到终点Y（大白应去的指定位置）为止，在这过程中用path记录扩展的路线，用min记录扩展过程中所经过的距离。

以此想法建立起模型，并称之为“两点间最短距离模型”。

4.3.2“两点间最短距离模型”的求解

针对问题二，要求两个确定点间的最短路径问题，采用数据结构里的最短路径算法,也叫Dijkstra算法,再运用MATLAB进行编程， MATLAB的编程程序见附录2，最后求得最短距离min与最短距离的行走路path如下，即A6 ?A8 ?A7 ?A11? A12 ?A1。线路图如图（3）所示：

图（3）

9

4.4.1“最近插入法模型”的建立

针对问题三，我们所提出的实际问题是：要使大白在最短的时间内走完所有的地点，即相当于求所有点都连接起来的最短距离。有些地点有好几条不同的线路可以走，要使行走过所有点的距离最短，就要使有多条线路可走的地点走最短的线路。再结合“中国邮递员问题”，从而建立了“最近插入法模型”。

4.4.2“最近插入法模型”的求解

针对问题三的求解，还是先考虑到了A3这个只有一条线路可走的地点。则由A3出发，大白在每一地点遇岔路时，则优先行走路径短的岔路；若岔路的路径等长，则优先行走通往未走过地点多的岔路。这样就得到了一条路线，在此基础上，通过观察分析计算对上述结果进行修正，然后，再采用穷举法对问题结果进行验证，结果与最终答案相吻合，最后确定了问题一的最优路线为：A3 ?A2? A1? A12? A11? A10 ?A13 ?A4 ?A5 ?A9? A8 ?A7 ?A8 ?A6。如图（4）所示：

图（4）

10

五、模型的评价与改进方向

5.1模型的优点：

1.优点在于利用matlab、lingo软件程序大大节约了计算量。 2.模型配予图片分析，形象化，直观，形象，易理解。 3.语言、符号简单. 5.2模型的缺点：

模型相对理想化，忽略了道路、环境、机器等影响因素。 5.3模型的改进方向：

对于不可避免的误差纳入计算，使结果更加贴近生活、真实化。

六、参考文献

[1].傅家良.运筹学方法与模型[M].上海,复旦大学出版社.2006年； [2].刘来福，曾文艺.数学模型与数学建模（第二版）.北京：北京师范大学出版社，2002； [3].蔡锁章.数学建模原理与方法.北京：海洋出版社；

11

七、附录

附录1： 学校地图：

68794511101311223

12