最短路问题专题_第1页
最短路问题专题_第2页
最短路问题专题_第3页
最短路问题专题_第4页
最短路问题专题_第5页
已阅读5页，还剩3页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

1、最短路问题算法及应用 1 问题描述 2 算法介绍 2.1 dijkstra算法 2.2 floyd算法 3 应用举例 3.1 物流中心选址 3.2 物流配送问题 3.3 多目标运输问题主要内容定义1 对简单图G的每一边e赋予一个实数，记为w(e)，称为边e的 权，而每边都赋予权的图称为赋权图。定义2 (u,v)-路的边权之和称为该路的长，而u,v间路长达到最小的 路称顶点u和v的最短路。在给定赋权图G中，求两个互异顶点间的最短路，简记为最短路问题。 最短路问题是最优化问题之一，广泛应用于生产实践中的许多问题，如线路安排、厂区选址、设备更新等。 1 问题描述 基本思想：按距离u0由近及远为顺序，

2、依次求得u0到G的各顶点的最短路和距离，直到v0(或直到G的所有顶点)，算法结束。2 算法介绍-dijkstra算法 算法步骤：初始化(i=0)：S0=vs，P(vs)=0, (vs)=0，对每一个vvs,令T(v)=+, (v)=M，k=sStep1：如果Si=V，算法终止，否则转入step2；Step2：考察每个使(vk,vj) A且vj不属于Si的点vj。如果T(vj)P(vk)+wkj，则把T(vj)修改为P(vk)+wkj，把 (vj)修改为k，否则转入step3；Step3：令T(vji)=minT(vj)| vj不属于Si。如果T(vji)dik+dkj，则令dij=dik+dk

3、j；Step3：若dii0，则存在一条含有顶点vi的负回路，停止；或者k=n停止，否则转入step2. Matlab程序（见附件） 3.1 物流中心选址3 应用举例 步骤： 求出最短路径矩阵U； 矩阵U每一行求和； 最小值行标号为选址地点。参考文献： F I oyd最短路径算法在配送中心选址中的应用，湖南农业大学学报 Matlab程序（见附件） 3.2 物流配送问题3 应用举例 问题抽象：物流配送问题可以抽象为必须通过指定点的最短路问题。 分两种情况：车辆回到原点；车辆不回到原点。举例：考虑2点的情况 由始点k1到终点k2，经过指定点t1、t2的最短路经过4个顶点的顺序只能是如下两种情况，k1t1t2k2和k1t2t1k2. 若要满足所求得的路是最短路，那么4个顶点中相邻顶点之间的路也一定是最短路。 于是分别计算k1t1，t1t2，t2k2和k1t2，t2t1，t1k2之间的最短路；然后前三者相加得d1，后三者相加得d2，比较d1与d2之值，取较小者作为最终的输出结果。 由此可以看出，算法的时间与随问题规模增大呈指数增长，所以最短路算法不适合大规模配送问题求解。 考虑经过2点的Matlab程序（见附件）

人人文库> 全部分类> 教育资料 > 备课教案

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论