论文总字数：11412字

摘 要

物流业的发展成为国民经济的一个新的增长点，对于物流公司来说，经常遇到把货物送到一个或多个地方的情况，在已有条件下如何使得费用最低，效果最好，成为配送的核心问题。本文阐述了Dijkstra算法和Floyd算法的基本思路，将二者运用到运输最短路径的选择实例中，以节约成本，提高产品竞争力。

关键词：物流配送，最短路径，Dijkstra算法，Floyd算法

Abstract：The development of logistics industry becomes the national economy a new growth point, for logistics companies, often encounter the goods to be delivered to one or more places, under the existing conditions, how to make the cost become the minimum and the effect become the best has been the core of distribution problems. In this paper, the basic idea of Dijkstra algorithm and Floyd algorithm are applied to be an example of the selection of transport shortest path in, in order to save costs and enhance the competitiveness of their products. 

Keywords：logistics,optimal path, Dijkstra algorithm,Floyd algorithm

目 录

1 引言 4

2 物流配送及其最短路径问题 4

3 迪杰斯特拉算法在物流配送中的应用 5

3.1 算法思想 5

3.2 算法执行过程 5

3.3 迪杰斯特拉算法在电子商务物流配送中的应用实例 6

3.3.1 问题背景 6

3.3.2 实际物流配送问题分析 7

3.4 运用C 实现迪杰斯特拉算法 9

3.4.1 C 的特点 9

3.4.2 迪杰斯特拉算法的C 实现 9

3.5 迪杰斯特拉算法时间复杂度分析 12

4 弗洛伊德算法在物流配送中的应用 12

4.1 算法思想 12

4.2 基于弗洛伊德算法的各城市之间最廉价航线选取 13

4.3 弗洛伊德算法的伪代码分析 14

4.4 弗洛伊德算法的时间复杂度分析 16

结论 17

参考文献 18

致谢 19

1 引言

在竞争日益激烈的现代商业社会，企业只有以市场为核心去适应不断变化的环境并及时对市场做出反应，才能在竞争中立于不败之地。物流管理正是以实现上述要求为目标，而物流配送是现代化物流管理中的一个重要环节。它是指按用户的定货要求，在配送中心进行分货、配货，并将配好的货物及时送交收货人的活动。在物流配送业务中，存在许多优化决策的问题。本文只讨论物流配送最短路径问题。合理选择配送路径，对加快配送速度、提高服务质量、降低配送成本以及增加经济效益都有很大影响。

2 物流配送及其最短路径问题

物流配送，即从商品流通的经营方式看的一种商品流通方式。也是一种现代的流通方式。现代物流实用词典说“物流配送”是共同化的服务模式，物流配送共同化，包括物流资源利用共同化、物流设施与设备利用共同化、物流管理共同化等等。详细来说，物流配送是物流活动中一种非单一的业务形式，它与商流、物流、资金流紧密结合，并且主要包括了商流活动、物流活动和资金流活动，可以说它是包括了物流活动中大多数必要因素的一种业务形式。

最短路径问题是物流配送中的一个重要问题，它也成为不同领域专家学者共同关注的问题。

最短路径算法是图论中的核心问题之一，它是许多更深层次算法的基础，同时，该问题有着大量的生产实际的背景。很多问题从表面上看与最短问题没有什么关系，却也可以归结为最短路问题。本文从算法思想、算法执行过程、时间复杂度以及算法的代码实现等方面对迪杰斯特拉算法和佛洛伊德算法进行了综合探究，并将二者进行比较，得出相关结论，从而实现算法在现实生活中的应用，体现其设计价值。

迪杰斯特拉算法是由荷兰计算机科学家狄克斯特拉于1959 年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决的是有向图中最短路径问题。迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。同时，迪杰斯特拉算法是一种标号法，给赋权图的每一个顶点记一个数，称为顶点的标号（临时符号，称为T标号，或者固定标号，称为P标号）。T标号表示从始顶点到该标号的最短路长的上界；P标号则是从始顶点到该顶点的最短路长。

弗洛伊德算法又称为插点法，是一种用于寻找给定的加权图中多源点之间最短路径的算法。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。Floyd算法是一种著名的解决任意两点间的最短路径（All Paris Shortest Paths，APSP）的算法。一般的Floyd算法在通用路径选择算法中，对最短路径的衡量标准是通过计算通过路径的时间作为图中边的权值，如何确定权值，直接决定了算法的适用性与优劣程度^[1]。从表面上粗看，Floyd算法是一个非常简单的三重循环，而且纯粹的Floyd算法的循环体内的语句也十分简洁。正是由于“Floyd算法是一种动态规划（Dynamic Programming）算法”的本质，才导致了Floyd算法如此精妙。因此，本文将从Floyd算法的状态定义、动态转移方程以及滚动数组等重要方面，来简单剖析一下图论中这一重要的基于动态规划的算法——Floyd算法。在动态规划算法中，处于首要位置、且也是核心理念之一的就是状态的定义。

3 迪杰斯特拉算法在物流配送中的应用

3.1 算法思想

设有两个顶点集合S和T，集合S中存放图中已找到最短路径的顶点，集合T存放图中剩余顶点。初始状态时，集合S中只包含源点，然后不断从集合T中选取到顶点路径长度最短的顶点并入到集合S中。集合S每并入一个新的顶点，都要修改顶点到集合T中顶点的最短路径长度值。不断重复此过程，直到集合T的顶点全部并入到S中为止。也就是，Dijkstra算法的主要思想是通过遍历整个图找到每个点的最短路径，从而确定目标点的最短路径。

3.2 算法执行过程

剩余内容已隐藏，请支付后下载全文，论文总字数：11412字