数学建模实验报告最短路问题及其算法.doc

最短路问题及其算法一.实验目的：1、了解与掌握图论的基本概念、相关MATLAB知识和最短路径算法；2、学会使用MATLAB编写Dijkstra算法和Floyd算法程序求最短路径.二.实验内容：要铺设一条A1A2A15的输送天然气的主管道，如图所示.经筛选后可以生产这种主管道的钢厂有S1，S2,S7.图中粗线表示铁路，单细线表示公路，双细线表示要铺设的管道（假设沿管道或者原来有公路，或者建有施工公路），圆圈表示火车站，每段铁路、公路和管道旁的阿拉伯数字表示里程（单位：km）.为方便计，1km主管道钢管称为1单位钢管.一个钢厂如果承担制造这种钢管，至少需要生产500单位钢厂在指定期限内能生产刚钢管的最大数量为个单位.钢管出厂销价1单位钢管为万元，如下表：1234567800800100020002000200030001601551551601551501601单位钢管的铁路运价如下表：里程（km） 300301-350351-40