最短路径问题-数学建模_第1页
最短路径问题-数学建模_第2页
最短路径问题-数学建模_第3页
最短路径问题-数学建模_第4页
最短路径问题-数学建模_第5页
已阅读5页，还剩12页未读， 继续免费阅读

下载本文档

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

文档简介

1、Floyd算法Dijkstra算法两个例子的求解引例2：最廉价航费表的制定引例1：最短运输路线问题最短路径问题的0-1规划模型3102374116598140504025105001520251501020402010010252520100551025255505l定义：设定义：设P(u,v)是加权图是加权图G中从中从u到到v的路径的路径,则该路则该路径上的边权之和称为该路径的权径上的边权之和称为该路径的权,记为记为w(P). 从从u到到v的路径中权最小者的路径中权最小者 P*(u,v)称为称为u到到v的最短路径的最短路径.10237411659811023741165981算法步骤算法步骤

2、S: 具有永久标号的顶点集具有永久标号的顶点集;l(v): v的标记的标记; f(v):v的父顶点的父顶点,用以确定最短路径用以确定最短路径; 输入加权图的带权邻接矩阵输入加权图的带权邻接矩阵w=w(vi,vj)nxm.初始化初始化 令令l(v0)=0,S= ; v v0 ,l(v)= ;更新更新l(v), f(v) 寻找不在寻找不在S中的顶点中的顶点u,使使l(u)为最小为最小.把把u加入到加入到S中中,然后对所有不在然后对所有不在S中的顶点中的顶点v,如如l(v)l(u)+w(u,v),则则更新更新l(v),f(v), 即即 l(v)l(u)+w(u,v),f(v)u;1)重复步骤重复步骤

3、2), 直到所有顶点都在直到所有顶点都在S中为止中为止.91023741165981算法步骤算法步骤 d(i,j) : i到到j的距离的距离; path(i,j): i到到j的路径上的路径上i的后继点的后继点; 输入带权邻接矩阵输入带权邻接矩阵a(i,j).1）赋初值）赋初值 对所有对所有i,j, d(i,j)a(i,j) , path(i,j)j,k=l.2）更新）更新d(i,j) , path(i,j) 对所有对所有i,j, 若若d(i,k)+d(k,j)d(i,j),则则 d(i,j)d(i,k)+d(k,j) , path(i,j)path(i,k) , k k+13）重复）重复2)直到直到k=n+11314102374116598115运行上页程序输出：运行上页程序输出：dis = 21path = 1 8 9 10 11 因此顶点因此顶点1到顶点到顶点11的最短路径为的最短路径为18 9 10 11, 其长度为其长度为21。160504025105001520251501020402010010252520100551025255

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

温馨提示

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

最新文档

评论

0/150

提交评论