MATLAB编程算法求解最短路问题.pdfVIP

组合优化实验报告 实验序号： 日期： 班级 姓名 学号 实验名称 最短路问题 实验所用软件及版本 Matlab R2008b 1、实验目的 1．掌握最短路问题的一种求解算法，并能编程实现该算法. 2、实验内容 1．（4 分）如图1所示，节点1、2、3 的坐标分别为(1,1)、(2,2.3)、(3.1,0.9)，根据各节 点的坐标用matlab 在2 维坐标上画出3个节点. y 2 1 3 o 图 x 1 2、（4 分）用matlab 编程求出图1 中任意两个节点之间的距离，并用邻接矩阵A 存储 并输出邻接矩阵A .邻接矩阵A 举例如下  0 w12 w13   A w 0 w  21 23  w w 0   31 32  3、（4 分）根据邻接矩阵A 编程求解出节点1到节点2 和节点3 的最短路，并画出最短 路的树形图，假设如图2 y 2 1 3 o x 图 2 4．（8分）附件 “50node.txt”（数据来源于贝尔实验室）为50个城市的坐标，编程求解 由第 1个城市到其它各城市的最短路，给出最短路的树形图. 3、详细设计 题 1 1).源代码 ： a=[1 1;2 2.3;3.1 0.9];% node坐标矩阵 plot(a(,1),a(,2),o)%画图 2).运行结果 ： 题 2 (1).源代码 a=[1 1;2 2.3 ;3.1 0.9]; [X,Y]=size(a); h = meshgrid(1X);%meshgrid是MATLAB中用于生成网格采样点的函数 A= reshape(sqrt(sum((a(h,)-a(h,)).^2,2)),X,X);% A(find(A==0))=inf%构造权矩阵A (2)运行结果 A = Inf 1.6401 2.1024 1.6401 Inf 1.7804 2.1024 1.7804 Inf 题 3 (1).源代码 ： function [P,D]=dijkstra_zd(A,sv) clear clc %Dijkstra法求解最短路 %A为邻接矩阵 ； %sv为寻求最短路的起始点 %P为所有点的P标号 ，即路权值 %D为sv到所有结点的最短路径矩阵 clear clc a=[1