求网络中任意两点最短路径 2

《求网络中任意两点最短路径 2》由会员分享，可在线阅读，更多相关《求网络中任意两点最短路径 2（6页珍藏版）》请在金锄头文库上搜索。

1、 “求网络中任意两点最短路径求网络中任意两点最短路径”问题解决思路问题解决思路文澜学院 成思洁 1204070159（一）问题研究价值及分类（一）问题研究价值及分类最短路径问题旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。在日常生活中，如果需要常常往返 A 地区和 B 地区之间，我们最希望知道的可能是从 A 地区到 B 地区间的众多路径中，哪一条路径的路途最短。最短路径问题也是地理信息系 统网络分析中的最基本最关键的问题，在交通网络结构的分析，交通运输线路的选择，通 讯线路的建造与维护，运输货流的最小成本分析，城市公共交通网络的规划等，都有直接 应用的价值。 算法具体的形式包括：（）

2、确定起点的最短路径问题：即已知起始结点，求最短路径的问题。 （）确定终点的最短路径问题：与确定起点的问题相反，该问题是已知终结结点，求 最短路径的问题。在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同 于把所有路径方向反转的确定起点的问题。 （）确定起点终点的最短路径问题：即已知起点和终点，求两结点之间的最短路径。 （）全局最短路径问题：求图中所有的最短路径。（二）解决思路：（二）解决思路：Dijkstra 算法算法算法简介算法简介：以起始点为中心向外层层扩展，直到扩展到终点为止。算法功能算法功能：在程序中设置一个二维数组来存储任意两个顶点之间的边的权值，用户可以将 任意一个图的

3、信息通过键盘输入，然后再输入要查找的两个顶点，程序可以自动求出这两 个顶点之间的最短路径。原理原理：输入一个带权有向图G=（Vi， E） ,i= 0,1,2n， Vi 表示节点， E 表示边。 W是一个二维数组， 用来存储约束条件， W i,j 即是边(i,j) 的权值。当(i,j) E 时，W i,j 为一个非负权值， 表示从节点i 到j 有路径相连； 否则表示没有路径相连，此时W i,j 为无穷大。D i 表示从指定节点到节点Vi 的最短路径长度。设置一个顶 点的集合S， 开始时S 中仅有指定节点， 即源点， 然后不断运用贪心的策略，调整非S 集合中点的最短路径长度， 找到当前的最短路径节

4、点， 将其加入到集合S 中， 当S 集 合包含了所有可到达的节点， D i 中的值即为指定节点到各Vi 点的最短距离。每次新扩展一个距离最短的点，更新与其相邻的点的距离。当所有边权都为正时，由 于不会存在一个距离更短的没扩展过的点，所以这个点的距离永远不会再被改变，因而保 证了算法的正确性。根据这个原理，用Dijkstra求最短路的图不能有负权边，因为扩展到 负权边的时候会产生更短的距离，有可能就破坏了已经更新的点距离不会改变的性质。核心思想核心思想： 首先， 把所有节点分为两组。第一组包含已确定最短路径的节点； 第二组 包含尚未确定最短路径的节点。然后， 按最短路径长度递增的顺序把第二组的节

5、点转移 到第一组中去， 直到第一组中包含所有可到达的结点为止。此时， 第二组中的节点为不可到达节点。在这个过程中， 总保持从指定节点到第一组各节点的最短路径长度都不大 于从指定节点到第二组中任何节点的路径长度。实现流程图实现流程图：（三）以算法形式（三）以算法形式（1）为例，演示详细步骤）为例，演示详细步骤ABDEF632534235C如上图，设 A 为源点，求 A 到其他各顶点（B、C、D、E、F）的最短路 径。线上所标注为相邻线段之间的距离，即权值。（注：此图中，相邻顶点间 的距离与图中的目视长度不能一一对等）步骤S 集合中U 集合中 1进入 A，此时 S= 此时最短路径 AA=0 以 A

6、 为中间点，从 A 开始找U= AB=6 AC=3 A其他 U 中的顶点= 发现 AC=3 的权值为最短 2进入 C，此时 S= 此时最短路径 AA=0，AC=3 以 C 为中间点，从 AC=3 这条最短路径开始找U= ACB=5AB=6 此时到 B 权值为 ACB=5 ACD=6 ACE=7 AC其他 U 中的顶点= 发现 ACB=5 的权值为最 短 3进入 B，此时 S= 此时最短路径 AA=0，AC=3,ACB=5 以 B 为中间点，从 ACB 这条最短路径开始找U= ACBD=10ACD=6 ACB其他 U 中的顶点 = 发现 ACD=6 的权值为最 短 4进入 D，此时 S= 此时最

7、短路径 AA=0，AC=3,ACB=5,ACD=6 以 D 为中间点，从 ACD 这条最短路径开始找U= ACDE=8ACE=7 ACDF=9 发现 ACE=7 的权值为最 短 5进入 E，此时 S= 此时最短路径 AA=0，AC=3,ACB=5,ACD=6,ACE=7 以 E 为中间点，从 ACE 这条最短路径开始找U= ACEF=12ACDF =9 此时到 F 权值更改为 ACDF=9 发现 ACDF=9 权值为最 短 6进入 F，此时 S= 此时最短路径 AA=0，AC=3,ACB=5,ACD=6,ACE=7,A CDF=9U 集合已空，查找完毕（四）（四）Dijkstra算法案例分析算

8、法案例分析：在在物流配送中的应用物流配送中的应用 电子商务是依托于互联网和信息技术的一种新型商务活动。目前,我国的电子商务发展势头迅猛,已经成为国民经济中的重要组成部分。相对于新生的电子商务来说,物流配送出现得比较早但是真正把它当作一个完整的系统来研究还是在 20 世纪 50 年代初。电子商务公司的配送不仅面向批发商和零售商,还要直接面对大批的最终消费者,况且电子商务不受时间、地域的限制,因此较难形成集中的、有规模的配送流量,由此造成配送任务复杂而琐碎,成本居高不下。降低配送服务价格,就要解决电子商务公司与物流配送企业之间在配送服务价格之间的矛盾,需要双方的共同努力。一方面电子商务公司考虑配送

9、成本,尽量将网上销售的商品控制在与物流企业协议确定的配送范围之内,并尽量使之相对集中且形成规模。另一方面,物流配送企业应积极协作,选择最短路径作为配送路径降低配送成本,并加强管理,开源节流,降低物流成本和配送服务的价格,同时还应尽可能与电子商务公司建立长期稳定的协作关系,这样做有利于物流企业制定长远投资和服务计划,有利于加快新的物流配送技术的应用,加大配送渠道和设施的建设力度,最终有利于加快实现物流配送系统的信息化、自动化、网络化和智能化从长远看,有利于持续稳定地降低物流配送的成本和价格。一、最短路径法一、最短路径法采用图论中的最短路径算法来建立物流配送路径选择模型。它的主要思想是从代表两个顶

10、点的距离的权矩阵开始,每次插人一个顶点比较任意两点间的已知最短路径和插人顶点作为中间顶点时可能产生的路径距离,然后取较小值以得到新的距离权矩阵。当所有的顶点均作为顶点时,得到的最后的权矩阵就反映了所有顶点间的最短距离信息。最短距离者作为费用最小者,即最佳的选址位置。由于最短路径问题有着广泛的应用背景,国内外大量专家学者都对此问题进行了深入的研究。经典的图论与不断完善的计算机数据结构及算法的有效结合,使得新的最短路径算法不断涌现。据统计,目前提出的此类最短路径的算法大约有种。而等人对其中的 17 种进行了测试,结果显示有种效果比较好,它们分别是:TQQ(graph growthwith two

11、queues)、DKA(the the Dijkstrasalgorithmimplemented with doubl ebuckets)。其中 TQQ 算法的基础是图增长论,用两个 FIFO 队列实现了一个双端队列结构来支持搜索过程,较适合于计算单源点到其他所有点的最短距离。后两种算法则是基于 Dijkstra 算法,采用桶结构明显提高了永久标记点的搜索速度。二二、路径分析设计、路径分析设计实际生活中,城市道路网的表现形式一般为数字化的矢量地图,其网络空间特征的交叉路口坐标和道路位置坐标借助于地图上的图形来识别和解释的。要对城市道路网运用Dijkstra 算法求解最短路径,首先必须抽象城市

12、道路网络为网络图论中的网络图,另外,系统要求计算道路上任意两点间的最短路径,而传统 Dijkstra 算法求解范围局限于任意网络节点间,不能满足要求,必须进行改进。1.系统工作流程设计随着城市建设的加快,城市道路网络经常发生变化,为避免经常改写代码,增强程序的健壮性和提高最短路径分析的运算效率,系统一般直接从拓扑文件提取道路网的网络拓扑结构并加载到内存中,一旦道路更新后,仅需重新抽象城市道路网络为网络图并生成拓扑文件即可。(1)抽象城市道路为网络图。首先对城市道路进行编辑处理,使其与实际道路相符合,并进行拓扑检查,生成线与线相互交叉的道路图然后创建城市道路拓扑,拓扑关系构建了相邻弧段和结点之间

13、的关系最后生成道路网络拓扑文件,文件中定义了共属性特征如弧段的起始节点、终止节点,弧段长度等,为最短路径计算准备数据。(2)最短路径求解。首先读取城市道路网络图然后系统根据屏幕输入坐标,寻找道路网中的最近点作为最短路径分析的起点和终点,利用算法计算满足条件的弧段,并依顺序连接所有弧段最后裁剪起终点两端的多余部分,返回最短路径。(3)最短路径显示与漫游。Skyline 中通过程序接口读取计算结果,并在三维场景中进行显示和设定为路径,系统提供模型角色沿路径进行漫游浏览。算法计算满足条件的弧段,并依顺序连接所有弧段最后裁剪起终点两端的多余部分,返回最短路径。最短路径显示与漫游。中通过程序接口读取计算

14、结果,并在三维场景中进行显示和设定为路径,系统提供模型角色沿路径进行漫游浏览。2.数据存储结构设计ArcGIS 是 ESRI 公司开发的一套完整的 GIS 应用产品,它通过对地理现象、事件及其关系进行可视化表达,构建特定的应用,提升工作效率。系统通过它进行城市道路的拓扑创建工作,并生成拓扑文件,把城市道路网抽象为关系图。系统借助 ArcGIS 的开发引擎ArcEngine 快速访问道路拓扑图,并完成网络关系图的存储及最短路径计算。三三、路径效果分析、路径效果分析随着 3S 技术的飞速发展,“数字城市”成为更高层次的追求,人们越来越多地要求从三位空间处理问题。建立以配送为中心的物流服务体系。配送

15、是商品市场发展的产物随着大批量、少批次的物流配送活动逐步被小批量、多批次所取代,个性化、多样化的市场需求越来越占有更多的市场份额,配送已成为电子商务时代物流活动的中心环节和最终目的。因此,一系列物流活动必须围绕组织配送表现出活跃的市场机制。物流企业内部的所有部门和人员都应面向配送、面向市场、面向客户。此外,物流企业要改变单一送货的观念,协助电子商务公司完成售后服务,提供更多的增值服务。内容,如跟踪产品订单、提供销售统计和报表等。只有这样才能紧跟电子商务的步伐,不被市场所淘汰。物流配送时使用最短路径分析的算法设计，使得在配送时能够选择到配送点最短路径,降低配送成本。通过多次实验表明采用该算法准确、可靠,为路径分析在物流中的应用进一步扩展奠定了基础。