dijkstra算法实现综述

《dijkstra算法实现综述》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Dijkstra算法实现综述摘要：Dijkstra算法是典型的最短路径算法，用于计算一个结点到其他所有结点的最短路径。Dijkstra的变形和应用非常多,需要一定的时间和题量积累，通过改进获得精度较高的结果。一、前言最短路径问题是在给定的网络图中寻找出一条从起始点到目标点之间最短路径。最短路算法不仅在GIS的交通路线导航、路径分析领域应用广泛,在解决路径搜索相关的应用中也十分普遍,包括网络路由算法、机器人探路、人工智能、游戏设计等等。 最短路径是在很多的路径中，找寻行经距离最短、或者说所花费成本最少的路径。由於交通运输的便利与普及，

2、所以两地之间有发生运送或者资讯的传递下，最短路径(ShortestPath)的问题随时都可能会有需求产生。一般应用的领域涵盖很广泛，如物流配送、货运快递邮务信件配送、警力巡逻、消防救灾救护、设施规划、生产排程、电子电路、水管配置、行动通讯、及电脑网路等。二、技术说明：Dijkstra算法迪杰斯特拉算法是由荷兰计算机科学家狄克斯特拉于1959年提出的，因此又叫狄克斯特拉算法。Dijkstra经典算法是由计算机科学家EdsgerDijkstra在文献中提出的。它是一个图的搜索算法，解决带非负权重图的单元最短路径问题并产生一棵最短路径树。

3、该算法经常使用在网络路由和地理信息系统中。Dijkstra算法是典型的最短路径算法，用于计算一个结点到其他所有结点的最短路径。是从一个顶点到其余各顶点的最短路径算法，解决的是有向图中最短路径问题。Dijkstra算法的基本思想是以源点为圆心，按最短路径长度递增的顺序通过对路径长度迭代得到从源点到其他各目标结点的最短路径。迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法是典型的算法。Dijkstra算法是很有代表性的算法。Dijkstra一般的表述通常有两种方式，一种用永久和临时标号方式，一

4、种是用OPEN,CLOSE表的方式，这里均采用永久和临时标号的方式。注意该算法要求图中不存在负权边。其基本原理是：每次新扩展一个距离最短的点，更新与其相邻的点的距离。当所有边权都为正时，由于不会存在一个距离更短的没扩展过的点，所以这个点的距离永远不会再被改变，因而保证了算法的正确性。不过根据这个原理，用Dijkstra求最短路的图不能有负权边，因为扩展到负权边的时候会产生更短的距离，有可能就破坏了已经更新的点距离不会改变的性质。具体如下：（1）算法分配给每个节点一个初步的距离值：设置初始节点为零和其他节点为无穷；（2）将当前访问节点

5、设置为初始节点，其他的所有节点设置为未访问节点，并创建一个未访问节点集合；（3）针对当前节点，计算其与所有邻接节点的距离。将计算出来的距离值与当前值进行比较，指定较小的一个。（4）当我们考虑完当前节点的所有邻接节点，标记当前为已访问，并将其从未访问集合删除。已访问节点将永远不会被访问；（5）选择为访问过的标记最小试探距离的节点，并将其作为新的当前节点，然后回到步骤3；（6）如果终止节点已标记访问或者最小试探性距离在未设置节点之间是无限的，该算法已完成。　举例来说，如果图中的顶点表示城市，而边上的权重表示著城市间开车行经的距离。Dij

6、kstra算法可以用来找到两个城市之间的最短路径。　　Dijkstra算法的输入包含了一个有权重的有向图G，以及G中的一个来源顶点S。我们以V表示G中所有顶点的集合。每一个图中的边，都是两个顶点所形成的有序元素对。(u,v)表示从顶点u到v有路径相连。我们以E所有边的集合，而边的权重则由权重函数w:E→[0,∞]定义。因此，w(u,v)就是从顶点u到顶点v的非负花费值(cost)。边的花费可以想像成两个顶点之间的距离。任两点间路径的花费值，就是该路径上所有边的花费值总和。已知有V中有顶点s及t，Dijkstra算法可以找到s到t的最

7、低花费路径(i.e.最短路径)。这个算法也可以在一个图中，找到从一个顶点s到任何其他顶点的最短路径。算法描述　　这个算法是通过为每个顶点v保留目前为止所找到的从s到v的最短路径来工作的。初始时，源点s的路径长度值被赋为0（d[s]=0），同时把所有其他顶点的路径长度设为无穷大，即表示我们不知道任何通向这些顶点的路径（对于V中所有顶点v除s外d[v]=∞）。当算法结束时，d[v]中储存的便是从s到v的最短路径，或者如果路径不存在的话是无穷大。Dijstra算法的基础操作是边的拓展：如果存在一条从u到v的边，那么从s到u的最短路径可以通

8、过将边(u,v)添加到尾部来拓展一条从s到v的路径。这条路径的长度是d[u]+w(u,v)。如果这个值比目前已知的d[v]的值要小，我们可以用新值来替代当前d[v]中的值。拓展边的操作一直执行到所有的d[v]都代表从s到v最短路径的花