【求解最短路径的相关算法概述2100字】

针对最短路径的算法，将其分为静态算法和动态算法。而本文研究的实际交通路网中的结点与道路信息，属于静态最短路径问题。所以，可以应用的主要算法包括Dijkstra算法、Floyd算法、A*算法等。在静态最短路径问题中，由荷兰科学家E.W.Dijkstra的Dijkstra算法，是使用最为广泛的算法之一。Dijkstra算法又称“迪克斯特拉算法”,主要应用于解决单源最短路径问题。算法基于贪心策略，运行的每一步都是最优解。而算法的特征是将起始点作为搜索的中心点，以圆形向外层层扩展搜索，一直向外延伸，直到将终点包含其中。搜索面积为以起始结点到终点的距离为半径的同心圆面积。搜索结果十分精确，保证了路径质量。而在这个过程中，不能出现负权值，否则算法在运行中，将道路网中的结点分为三种类型：未标记的结点、临时标记的结点以及永久标记的结点。而Dijkstra算法的思想是以起始点为根基，遍历起始点周围所用的结点，将其中最短的结点标记为永久标记结点，并以此结点为下一个根基，重复以上过程，直到搜索到终点为止。而在遍历的过程中，其余较短的结点均存于临时标记的结点中，未经遍历的结点存于未标记的结点中。值得一提的是，在Dijkstra算法中，临时标记的结点在存储过程中是没有顺序的。所以，Dijkstra算法每运行一次，查找一次最短路径，都必须将所以的临时标记的结点进行遍历，这也是Dijkstra算法存在的问题。总而言之，Dijkstra算法是根据路径的权值的大小有序的生成的最短路径算法。算法步骤：(1)将所以结点初始化，将图中的所以结点变为未标记结点。同时，将起始结点置入CLOSE表中，其余结点置入OPEN表中。(2)取CLOSE表中的最后一个结点作为当前结点，查找OPEN表中的结点，判断两者之间的距离，有更小的权值就更新。(3)将具有最小权值的结点置入CLOSE表中，同时在OPEN表中删除该结点。(4)判断OPEN结点是否为空，如果为空，则重复以上步骤。(5)如果OPEN结点不为空，运算结束，输出最短路径。算法流程图：是否除此之外，算法仍存在几个不足：(1)在数据存储时，Dijkstra算法是采用邻接矩阵储存路网，其储存大小为n×n。因此，算法在计算最短路径的过程中进行了多次遍历，时间复杂度为O (n²)。虽然路网中的结点很多，但是与结点相连的结点数量并不多，即路网图为稀疏图。所以，邻接矩阵的存储方式对路网太过浪费，并计算了许多无意义的数据。所以，存储效率和计算效率极低。(2)在更新最小权值的过程中，需要比较所有在OPEN表中的结点数据，要进行大量重复操作，效率极低。(3)以圆形面积搜索，虽然精准，但搜索面积过大，十分浪费。Floyd算法又称“弗洛伊德算法”,由斯坦福教授罗伯特弗洛伊德创造9。此算法基于动态规划思想，旨在求算出在图中每一对结点之间的最短路径，也可将算法看成多次运算的Dijkstra算法，结构紧凑。值得一提的时，Floyd算法可以应用在边权值为负的图中，在稠密图中的运行效果最佳。算法步骤：(1)初始化图中所有的结点，并进行编号V₁、V₂、…Vn。同时，初始化矩阵Do。若结点Vi到Vj之间存在带有权值的相同的边，是两结点之间的距离。如果两结点之间不存在相通的边，则dij长度无穷大(∞);(2)对于每一对的顶点，采取递归公式：dj=min{dik+dkj,dj}其中k代表图中的结点，计算每对顶点之间的距离，当存在更短距离时进行更新。(3)算法结束后，矩阵Dn中的元素即表示结点之间的最短路径长度。由以上过程可以看出，该算法在计算的过程中，必须计算n个矩阵，而且每个矩阵含有n×n个元素，所以其时间复杂度为0(n³)。由于Floyd算法和Dijkstra算法类似，对这两种算法的基本情况进行归纳和Dijkstra算法Fl适用范围有向图和无向图有向图和无向图功能可以用于单源单汇最短路径用于求所有顶点之间的最短问题路径时间复杂度正权值正权值和负权值联系Floyd算法可以用重复的n次Dijkstra算法来代替表1:算法对比除了前两种算法之外，由Hart等人提出的搜索算法一—A*算法，也是一种比较智能和经典的算法。如果将Dijkstra算法看为基础，那么A*算法就是在此基础上生成的创新之花。A*算法的闪亮之处在于在原有的基础上加入了启发式机制，引入一个估价函数。这不仅是将未搜索点与起始结点之间的关系考虑进去，也将未搜索点与终点之间的关系也考虑在内，以此来保证搜素方向是不断向终点方向进行的，大大的提高了搜索的效率。A*算法的启发函数如下：式中：F(n)代表结点n的代价；G(n)表示从起始结点到结点n的实际花费代价；H(n)是从结点到终点的预估代价。所以，A*算法将实际花费代价与终止结点代价估值一同考虑在内，改进了Dijkstra算法的盲目性，有效减少搜索节点数，提高效率。NN从上可以看出，对OPEN表中和CLOSE表中结点