毕业论文移动版

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

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

迪杰斯特拉算法是由荷兰计算机科学家狄克斯特拉于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  算法执行过程 

    首先引进3个辅助数组dist[]、path[]、set[]。dist[ ]表示当前已找到的从 到每个终点 的最短路径的长度。它的初态为：若从 到 有边，则dist[ ]为边上的权值，否则置dist[ ]为 。path[ ]中保存从 到 最短路径上 的前一个顶点，假设最短路径上的顶点序列为 ，则path[ ]= 。path[]的初态为：如果 到 有边，则path[ ]= ,否则path[ ]=-1。set[]为标记数组，set[ ]=0表示 在T中，即没有被并入最短路径；set[ ]=1表示 在S中，即已经被并入最短路径。set[]初态为：set[ ]=1,其余元素全为0。具体步骤如下：

(1) 从当前dist[]数组中选出最小值，假设为dist[ ]，将set[ ]设置为1，表示当前新并入的顶点为 。 (责任编辑：qin)