Dijkstra算法

出自 MBA智库百科(https://wiki.mbalib.com/)

Dijkstra算法（狄克斯特拉算法）

　　Dijkstra算法是由荷兰计算机科学家狄克斯特拉（Dijkstra）于1959 年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决的是有向图中最短路径问题。

　　其基本原理是：每次新扩展一个距离最短的点，更新与其相邻的点的距离。当所有边权都为正时，由于不会存在一个距离更短的没扩展过的点，所以这个点的距离永远不会再被改变，因而保证了算法的正确性。不过根据这个原理，用Dijkstra求最短路的图不能有负权边，因为扩展到负权边的时候会产生更短的距离，有可能就破坏了已经更新的点距离不会改变的性质。

　　举例来说，如果图中的顶点表示城市，而边上的权重表示著城市间开车行经的距离。 Dijkstra算法可以用来找到两个城市之间的最短路径。

　　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的最低花费路径(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的最短路径可以通过将边(u,v)添加到尾部来拓展一条从s到v的路径。这条路径的长度是d[u]+w(u,v)。如果这个值比目前已知的d[v]的值要小，我们可以用新值来替代当前d[v]中的值。拓展边的操作一直执行到所有的d[v]都代表从s到v最短路径的花费。这个算法经过组织因而当d[u]达到它最终的值的时候没条边(u,v)都只被拓展一次。

　　算法维护两个顶点集S和Q。集合S保留了我们已知的所有d[v]的值已经是最短路径的值顶点，而集合Q则保留其他所有顶点。集合S初始状态为空，而后每一步都有一个顶点从Q移动到S。这个被选择的顶点是Q中拥有最小的d[u]值的顶点。当一个顶点u从Q中转移到了S中，算法对每条外接边(u,v)进行拓展。

　　在下面的算法中,u:=Extract_Min(Q)在在顶点集Q中搜索有最小的d[u]值的顶点u。这个顶点被从集合Q中删除并返回给用户。

 1  function Dijkstra(G, w, s)
 2     for each vertex v in V[G]                        // 初始化
 3           d[v] := infinity
 4           previous[v] := undefined
 5     d[s] := 0
 6     S := empty set
 7     Q := set of all vertices
 8     while Q is not an empty set                      // Dijstra算法主体
 9           u := Extract_Min(Q)
10           S := S union {u}
11           for each edge (u,v) outgoing from u
12                  if d[v] > d[u] + w(u,v)             // 拓展边(u,v)
13                        d[v] := d[u] + w(u,v)
14                        previous[v] := u

　　如果我们只对在s和t之间寻找一条最短路径的话，我们可以在第9行添加条件如果满足u=t的话终止程序。

　　现在我们可以通过迭代来回溯出s到t的最短路径

1 S := empty sequence 
2 u := t
3 while defined u                                        
4       insert u to the beginning of S
5       u := previous[u]

　　现在序列S就是从s到t的最短路径的顶点集.

　　我们可以用大O符号将Dijkstra算法的运行时间表示为边数m和顶点数n的函数。

　　Dijkstra算法最简单的实现方法是用一个链表或者数组来存储所有顶点的集合Q,所以搜索Q中最小元素的运算(Extract-Min(Q))只需要线性搜索Q中的所有元素。这样的话算法的运行时间是O(n2)。

　　对于边数少于n2稀疏图来说，我们可以用邻接表来更有效的实现Dijkstra算法。同时需要将一个二叉堆或者斐波纳契堆用作优先队列来寻找最小的顶点(Extract-Min)。当用到二叉堆的时候，算法所需的时间为O((m+n)log n)，斐波纳契堆能稍微提高一些性能，让算法运行时间达到O(m + n log n)。 相关问题和算法

　　在Dijkstra算法的基础上作一些改动，可以扩展其功能。例如，有时希望在求得最短路径的基础上再列出一些次短的路径。为此，可先在原图上计算出最短路径，然后从图中删去该路径中的某一条边，在余下的子图中重新计算最短路径。对于原最短路径中的每一条边，均可求得一条删去该边后子图的最短路径，这些路径经排序后即为原图的一系列次短路径。

　　OSPF（open shortest path first, 开放最短路径优先）算法是Dijkstra算法在网络路由中的一个具体实现。

　　与Dijkstra算法不同，Bellman-Ford算法可用于具有负花费边的图，只要图中不存在总花费为负值且从源点 s 可达的环路（如果有这样的环路，则最短路径不存在，因为沿环路循环多次即可无限制的降低总花费）。

　　与最短路径问题有关的一个问题是旅行商问题(traveling salesman problem)，它要求找出通过所有顶点恰好一次且最终回到源点的最短路径。该问题是NP难的；换言之，与最短路径问题不同，旅行商问题不太可能具有多项式时间算法。

　　如果有已知信息可用来估计某一点到目标点的距离，则可改用A*算法，以减小最短路径的搜索范围。

　　电子商务是依托于互联网和信息技术的一种新型商务活动。目前,我国的电子商务发展势头迅猛,已经成为国民经济中的重要组成部分。相对于新生的电子商务来说,物流配送出现得比较早但是真正把它当作一个完整的系统来研究还是在20世纪50年代初。

　　在电子商务尤其是B2C业务开展之初,国内还没有一家物流公司具有电子商务的配送经验,各个电子商务公司只能求助于具有国内最大覆盖网络的中国邮政速递公司,EMS但是在经历一段时间之后,EMS由于自身体制的僵化分割,管理无法协调、服务水平无法提高、费用居高不下,对很多问题都是心有余而力不足,无法满足电子商务发展的快速要求。

　　鉴于此种情景,国内的许多大型电子商务公司都在积极地寻找出路,有的自己投资组建配送队伍,但是要将自己的网点覆盖全国实在太难、投资太大有的积极寻找新近进人电子商务配送领域的配送公司,但是后来者的实力和发展速度着实无法满足需求也有求助传统的第三方物流公司,在电子商务覆盖需求如此广大,服务环节如此复杂,业务特点往往品种多、数量少、利润低等实际问题面前,传统的物流公司往往是望而却步。

　　商品配送成本过高电子商务公司的配送不仅面向批发商和零售商,还要直接面对大批的最终消费者,况且电子商务不受时间、地域的限制,因此较难形成集中的、有规模的配送流量,由此造成配送任务复杂而琐碎,成本居高不下。降低配送服务价格,就要解决电子商务公司与物流配送企业之间在配送服务价格之间的矛盾,需要双方的共同努力。

　　一方面电子商务公司考虑配送成本,尽量将网上销售的商品控制在与物流企业协议确定的配送范围之内,并尽量使之相对集中且形成规模。

　　另一方面,物流配送企业应积极协作,选择最短路径作为配送路径降低配送成本,并加强管理,开源节流,降低物流成本和配送服务的价格,同时还应尽可能与电子商务公司建立长期稳定的协作关系,这样做有利于物流企业制定长远投资和服务计划,有利于加快新的物流配送技术的应用,加大配送渠道和设施的建设力度,最终有利于加快实现物流配送系统的信息化、自动化、网络化和智能化从长远看,有利于持续稳定地降低物流配送的成本和价格。

　　目前关于物流配送的问题已经有很多方法,大致可分为定性和定量两大类。定性方法是指凭借个人或集体的经验来做出决策,它的执行步骤一般是先根据经验确定评价指标对各待选中心利用评价指标进行优劣性检验,根据检验结果作出决策。

　　定性方法的优点是注重历史经验、简单易行,其缺点是容易犯经验主义和主观主义的错误,并且当可选地点较多时不易做出理想的决策。定量方法根据各种约束条件和所要达到的目标,把选址问题转化为函数,再利用合适的算法进行求解,求出最符合条件的解即具体的地点作为配送路径。基于最短距离改进问题的算法的物流配。

　　一、最短路径法

　　采用图论中的最短路径算法来建立物流配送路径选择模型。它的主要思想是从代表两个顶点的距离的权矩阵开始,每次插人一个顶点比较任意两点间的已知最短路径和插人顶点作为中间顶点时可能产生的路径距离,然后取较小值以得到新的距离权矩阵。当所有的顶点均作为顶点时,得到的最后的权矩阵就反映了所有顶点间的最短距离信息。最短距离者作为费用最小者,即最佳的选址位置。

　　由于最短路径问题有着广泛的应用背景,国内外大量专家学者都对此问题进行了深入的研究。经典的图论与不断完善的计算机数据结构及算法的有效结合,使得新的最短路径算法不断涌现。据统计,目前提出的此类最短路径的算法大约有种。而等人对其中的17种进行了测试,结果显示有种效果比较好,它们分别是:TQQ(graph growthwith two queues)、DKA(the the Dijkstra'salgorithmimplemented with doubl ebuckets)。其中TQQ算法的基础是图增长论,用两个FIFO队列实现了一个双端队列结构来支持搜索过程,较适合于计算单源点到其他所有点的最短距离。后两种算法则是基于Dijkstra算法,采用桶结构明显提高了永久标记点的搜索速度。

　　二、算法原理及应用

　　算法是由荷兰计算机科学家艾兹格·迪科斯彻提出的,可用来找出图中指定节点到其他节点间的最短距离。其主要思想是首先从源点求出长度最短的一条路径,然后通过对路径长度迭代得到从源点到其他各目标节点的最短路径。具体求解过程如下:

　　设wj是从源点s到节点j的最短路径长度pj是从s到的最短路径中j点的前一节点。是标识集合。是未标识集合是节点集合。dij是节点i到节点j的距离(i与j直接相连,否则)。

　　(1)S={s}；T=M-S；w_j=ds；(,s与j直接相连)或,s与j不直接相连)。

　　(2)在T找节点i，使s到i的距离最小，并将i划归到S(可从与s直接相连的j中考虑)。若d_{ai}=mind_{aj}(i\inT),j与s直接相连,则将划归到中,即,,二修改中节点的值,若值改变,则。

　　(3)修改T中j节点的w_j值:wj = min(wj,w_i + dij)　；若wj值改变,则p_j = i。

　　(4)选定所有的wj最小值,并将其划归到S中这样就得到一个与供应商、工厂及用户间的最短距离,在费用、时间等方面的花费也相对要小得多,故可以将该物流中心选在该点处。

　　w_i = minw_j()；{i}；T=T{i}；若,所有节点已标识,则算法终止,否则,转人步骤(3)。

　　Dijkstra算法通用性强,既可以解决单源点间的最短路径问题,也可解决所有点对之间的最短路径问题,且编程简单。将物流中心选在与所有点对距离最近的那个点即可。

　　三、路径分析设计

　　实际生活中,城市道路网的表现形式一般为数字化的矢量地图,其网络空间特征的交叉路口坐标和道路位置坐标借助于地图上的图形来识别和解释的。要对城市道路网运用Dijkstra算法求解最短路径,首先必须抽象城市道路网络为网络图论中的网络图,另外,系统要求计算道路上任意两点间的最短路径,而传统Dijkstra算法求解范围局限于任意网络节点间,不能满足要求,必须进行改进。

　　1.系统工作流程设计

　　随着城市建设的加快,城市道路网络经常发生变化,为避免经常改写代码,增强程序的健壮性和提高最短路径分析的运算效率,系统一般直接从拓扑文件提取道路网的网络拓扑结构并加载到内存中,一旦道路更新后,仅需重新抽象城市道路网络为网络图并生成拓扑文件即可。

　　(1)抽象城市道路为网络图。首先对城市道路进行编辑处理,使其与实际道路相符合,并进行拓扑检查,生成线与线相互交叉的道路图然后创建城市道路拓扑,拓扑关系构建了相邻弧段和结点之间的关系最后生成道路网络拓扑文件,文件中定义了共属性特征如弧段的起始节点、终止节点,弧段长度等,为最短路径计算准备数据。

　　(2)最短路径求解。首先读取城市道路网络图然后系统根据屏幕输入坐标,寻找道路网中的最近点作为最短路径分析的起点和终点,利用算法计算满足条件的弧段,并依顺序连接所有弧段最后裁剪起终点两端的多余部分,返回最短路径。

　　(3)最短路径显示与漫游。Skyline中通过程序接口读取计算结果,并在三维场景中进行显示和设定为路径,系统提供模型角色沿路径进行漫游浏览。算法计算满足条件的弧段,并依顺序连接所有弧段最后裁剪起终点两端的多余部分,返回最短路径。最短路径显示与漫游。中通过程序接口读取计算结果,并在三维场景中进行显示和设定为路径,系统提供模型角色沿路径进行漫游浏览。

　　2.数据存储结构设计

　　ArcGIS是ESRI公司开发的一套完整的GIS应用产品,它通过对地理现象、事件及其关系进行可视化表达,构建特定的应用,提升工作效率。系统通过它进行城市道路的拓扑创建工作,并生成拓扑文件,把城市道路网抽象为关系图。系统借助ArcGIS的开发引擎ArcEngine快速访问道路拓扑图,并创建以下几个类完成网络关系图的存储及最短路径计算,如表所示。

　　四、路径效果分析

随着3S技术的飞速发展,“数字城市”成为更高层次的追求,人们越来越多地要求从三位空间处理问题。建立以配送为中心的物流服务体系。配送是商品市场发展的产物随着大批量、少批次的物流配送活动逐步被小批量、多批次所取代,个性化、多样化的市场需求越来越占有更多的市场份额,配送已成为电子商务时代物流活动的中心环节和最终目的。因此,一系列物流活动必须围绕组织配送表现出活跃的市场机制。物流企业内部的所有部门和人员都应面向配送、面向市场、面向客户。此外,物流企业要改变单一送货的观念,协助电子商务公司完成售后服务,提供更多的增值服务。内容,如跟踪产品订单、提供销售统计和报表等。只有这样才能紧跟电子商务的步伐,不被市场所淘汰。

　　物流配送时使用最短路径分析的算法设计。使得在配送时能够选择到配送点最短路径,降低配送成本。通过多次实验表明采用该算法准确、可靠,为路径分析在物流中的应用进一步扩展奠定了基础。