最短路径问题-数学建模06419.ppt

1、最短路径问题，Mathematica Modeling， 参考书：1.傅鸿龄刘琼荪何中市数学实验科学出版社2 .张绍民李淑华数据结构教程C语言版中国电力出版社发表：重庆大学出墙，主要内容，Floyd算法，Dijkstra算法，两个例子的解决引用例2 :最便宜的航空费用表的制作，引用例1 最短路径问题的0-1规划模型，a，3，如图所示的交通网络，各弧上的数字表示车辆在这条道路上行驶所需的时间，表示单向行驶的路，没有单向行驶的路表示双向行驶。 如果一辆货物从一号顶点运往十一号顶点，询问货车应该走哪条路线，能最早到达目的地？引用例1 :最短运输路线问题，a，4，一家公司在六个城市C1、C2、C3、C

2、4、C5、C6有分公司，公司的成员频繁地到达它们已知Ci到Cj的直达航班的费用由下述矩阵的第I行、第j列的要素给出(表示无直达航班)，该公司想计算任意两个城市间最便宜的路线运费表。 引用例2 :制作最便宜的航空费用表，a，5，最短路径问题，定义： P(u， 如果将v )设为加权图g中从u到v的路径，则该路径上的边权之和被称为该路径的权，记为w(P )，具有有向图、无向图、混合图的权非负.算法构想：采用标签作业法，每次反复生成永久标签，将v0 Dijkstra算法算法步骤，S:是具有永久标签的顶点集的l(v): v的标记f(v):v的父顶点。 确定最短路径输入权重图的加权邻接矩阵w=w(vi，v

3、j)nxm .初始化指令l(v0)=0，s=； vv0，l(v)=； 在s上加上u，对于不在s上的所有顶点v，例如l(v)l(u) w(u，v )，l(v )、f(v )即l(v)l(u) w(u，v )， 更新f(v)u .重复步骤2 )，直到所有顶点都进入MATLAB程序(Dijkstra算法)、function min，path=dijkstra(w，start，terminal ) n=si 标签(开始)=0； f (开始)=开始； fori=1: nmii=startlabel (I )=INF； 结束，结束s (1)=开始； u=start； 标签长度，标签长度，标签长度，标签长度

4、。 f(v)=u； 结束、结束、结束、v1=0； k=inf； for i=1:n ins=0； forj=1:长度(s ) ifi=s (j ) ins=1； 结束，结束if ins=0v=I； if标签(v ) k=标签(v ) v1=v； 结束、结束、结束s (长度(s )1)=v1； u=v1； end，min=label (终端)路径(1)=终端； i=1； 威尔路径(I )=开始路径(I1)=f (路径(I ) )； i=i 1； 结束路径(I )=开始； l=长度(路径)路径=路径(l :-1:1 )、a、9、最短路径算法、Dijkstra算法程序的使用说明：调用形式为min，path=dijkstra(w 返回从开始到终端的最短路径path及其长度min . 注意：顶点的编号从1开始连续。 另外，最短路径算法、Floyd算法使用范围：包含有向图、无向图、混合图的算法思想：以直接在图的加权相邻矩阵中插入顶点的方式来求出n个矩阵D(1)、D(2)、D(n ) Floyd算法算法程序，从d(i，j)