杨君子 张利民

[摘 要]最短路径算法不仅具有重要的理论意义，而且具有重要的实用价值，它应用于交通运输、设备更新、线路设计等各方面。本文介绍了Dijkstra算法，并针对衡水市某区域蔬菜农产品配送到小区超市要求路线最短问题，建立数学模型给出最佳方案。

[关键词]最短路径;Dijkstra算法;农产品

[中图分类号]F326.6 [文献标识码]A

最短路问题是图论中非常重要的最优化问题之一，它是一个在现实生活中经常被用到的基本工具，它可以解决现实生活中的许多实际问题，如城市中的管道铺设、交通运输、电子导航、线路安排、工厂布局、设备更新等。另外，它还可以解决最快路径问题、最低费用问题、邮政选址问题等其他最优化问题。最短路问题，一般来说就是从给定的网络图中找出任意两点之间距离最短的一条路，就是从图G中某对顶点vi和vj（i≠j）之间的所有路径中权值之和最短的一条路径作为顶点vi到頂点vj的最短路径。

1 Dijkstra算法

Dijkstra算法是在一个赋权有向图中能够寻找出最短路问题的最好方法，它是由荷兰计算机科学家E.W.Dijkstra在1959年提出来的，它适用于所有弧的权值为非负的情况（即wij≥0）。Dijkstra算法在图论中是一种典型的单源最短路径算法，可以用来计算从一个给定的节点vs到其他所有点中任意一个点vj的最短路。Dijkstra算法的基本思想：从指定的点vs出发，逐渐一层一层向外扩充去寻找最短路。

2 农产品配送最短路径问题

由于农产品中生鲜、鲜奶等时效性强，利用最短路径算……