利用Matlab编程计算最短路径及中位点选址
6页1、19.利用Mat lab编程计算最短路径及中位点选址1、最短路问题两个指定顶点之间的最短路径。例如,给出了一个连接若十个城镇的铁路网络,在这个网络的两个指定城镇 间,找一条最短铁路线。以各城镇为图G的顶点,两城镇间的直通铁路为图G相应两顶点间的边, 得图G。对G的每一边e,赋以一个实数w(e)一直通铁路的长度,称为e的权, 得到赋权图G。 G的子图的权是指子图的各边的权和。问题就是求赋权图G中 指定的两个顶点u ,v间的具最小权的轨。这条轨叫做u ,v间的最短路,它的权 0000叫做u , v间的距离,亦记作d(u , v )。0000求最短路已有成熟的算法:迪克斯特拉(Dijkstra)算法,其基本思想是按 距U0从近到远为顺序,依次求得U0到弓的各顶点的最短路和距离,直至V0 (或 直至G的所有顶点),算法结束。为避免重复并保留每一步的计算信息,采用了 标号算法。下面是该算法。(i) 令 l(u ) = 0,对 v。u,令 l(v) = 8,S = u ,i - 0。0000(ii) 对每个 v e S ( S = V Si),用minl (v), l (u) + w(uv) ue
2、Si代替l(v)。计算minl(v),把达到这个最小值的一个顶点记为 u+1,令S 广 S u u +11。(iii).若 i=W I1,停止;若 i 1V I1,用 i +1 代替 i,转(ii)。算法结束时,从u0到各顶点u的距离由u的最后一次的标号I(v)给出。在v进 入Si之前的标号1 (v)叫T标号,v进入Si时的标号l(v)叫P标号。算法就是不断 修改各项点的T标号,直至获得P标号。若在算法运行过程中,将每一顶点获 得P标号所由来的边在图上标明,则算法结束时,U0至各项点的最短路也在图 上标示出来了。例1:某公司在六个城市十,C中有分公司,从C到七的直接航程票 价记在下述矩阵的3)位置上。(8表示无直接航路),请帮助该公司设计一张 城市C1到其它城市间的票价最便宜的路线图。050840251050015208258150102084020100102525820100551025825550用矩阵气“顷为顶点个数)存放各边权的邻接矩阵,行向量pb、index1、 index2、d分别用来存放P标号信息、标号顶点顺序、标号顶点索引、最短通路 的值。其中分量1当第i顶点已标号P
《利用Matlab编程计算最短路径及中位点选址》由会员壹****1分享,可在线阅读,更多相关《利用Matlab编程计算最短路径及中位点选址》请在金锄头文库上搜索。
D-井盒气层压裂投产施工设计投球分压
家庭节约用水的建议
六年级优秀生练习题(1)
最新精选三篇银行员工个人工作计划范文
《商务沟通方法与技能》复习资料
医学运动系统英语词汇
税务工作者个人工作总结及工作思路范本(2篇).doc
基于无线传感器网络的远程环境监测系统的设计及实现
高速公路开工仪式领导讲话稿
四年级英语作文我的家我的家英语作文5句话
行政领导者的职责范文(2篇).doc
计算机爱课程设计——迷宫游戏
九年级物理教学计划汇总(2篇).doc
尊师守纪的演讲稿
疏浚工程设备项目立项报告
《相似三角形性质》说课稿
新密市关于成立城乡社区服务公司分析报告【参考模板】
年度个人工作总结模板(2篇).doc
某公司物流与采购管理系统
课程设计论文基于MATLAB的时序逻辑电路设计与仿真
2022-08-08 3页
2022-08-04 17页
2023-08-11 3页
2022-10-23 2页
2023-08-20 9页
2023-11-07 3页
2023-07-14 4页
2022-12-17 7页
2023-07-31 12页
2024-01-11 4页