基于matlab的floyd算法 matlab计算最短路径function [d,path]=floyd(a,sp,ep)
% floyd - 最短路问题
%
% Syntax: [d,path]=floyd(a,sp,ep)
%
% Inputs:
% a - 距离矩阵是指i到j之间的距离，可以是有向的
% sp - 起点的标号
% ep - 终点的标号
%
% Outputs:
% d - 最短路的距离
% path - 最短路的路径
%
a =[
0 50 inf;
50 0 15 ;
Inf 15 0 ];% a(i,j)，从节点i到j之间的距离
% [d,path]=floyd(a,2,5)
sp=3;
ep=1;
n=size(a,1);
D=a;
path=zeros(n,n);
for i=1:n
for j=1:n
if D(i,j)~=inf
path(i,j)=j; %j是i的后续点 end
end
end
for k=1:n
for i=1:n
for j=1:n
if D(i,j)>D(i,k)+D(k,j)
D(i,j)=D(i,k)+D(k,j);
path(i,j)=path(i,k);
end
end
end
end
p=[sp];
mp=sp;
for k=1:n
if mp~=ep
d=path(mp,ep); p=[p,d];
mp=d;
end
end
d=D(sp,ep)
path=p
试计算下图的最短路径，1.起点C点，终点A点。
2.起点A点，终点G点。
3.起点D点，终点F点。
试计算下图的最短路径，
1.起点F点，终点A点。
2. 起点E点，终点C点。
图论算法及其MATLAB 程序代码 求赋权图G =(V ,E ,F )中任意两点间的最短路的Warshall-Floyd 算法： 设A =(a ij )n ×n 为赋权图G =(V ,E ,F )的矩阵,当v i v j ∈E 时a ij =F (v i v j ),否则取a ii =0,a ij =+∞(i ≠j ),d ij 表示从v i 到v j 点的距离,r ij 表示从v i 到v j 点的最短路中一个点的编号. ①赋初值.对所有i ,j ,d ij =a ij ,r ij =j .k =1.转向② ②更新d ij ,r ij .对所有i ,j ,若d ik +d k j ＜d ij ,则令d ij =d ik +d k j ,r ij =k ,转向③. ③终止判断.若d ii ＜0,则存在一条含有顶点v i 的负回路,终止;或者k =n 终止;否则令k =k +1,转向②. 最短路线可由r ij 得到. 例1求图6-4中任意两点间的最短路. 解：用Warshall-Floyd 算法,MATLAB 程序代码如下： n=8;A=[0281Inf Inf Inf Inf 206Inf 1Inf Inf Inf 8607512Inf 1Inf 70Inf Inf 9Inf Inf 15Inf 03Inf 8 Inf Inf 1Inf 3046 Inf Inf 29Inf 403 Inf Inf Inf Inf 8630];%MATLAB 中,Inf 表示∞ D=A;%赋初值 for (i=1:n)for (j=1:n)R(i,j)=j;end ;end %赋路径初值 for (k=1:n)for (i=1:n)for (j=1:n)if (D(i,k)+D(k,j) 两个指定顶点之间的最短路径 问题如下：给出了一个连接若干个城镇的铁路网络，在这个网络的两个指定城镇间，找一条最短铁路线。 以各城镇为图G 的顶点，两城镇间的直通铁路为图G 相应两顶点间的边，得图G 。对G 的每一边e ，赋以一个实数)(e w —直通铁路的长度，称为e 的权，得到赋权图G 。G 的子图的权是指子图的各边的权和。问题就是求赋权图G 中指定的两个顶点00,v u 间的具最小权的轨。这条轨叫做00,v u 间的最短路，它的权叫做00,v u 间的距离，亦记作),(00v u d 。 求最短路已有成熟的算法：迪克斯特拉（Dijkstra ）算法，其基本思想是按距0u 从近到远为顺序，依次求得0u 到G 的各顶点的最短路和距离，直至0v （或直至G 的所有顶点），算法结束。为避免重复并保留每一步的计算信息，采用了标号算法。下面是该算法。 (i) 令0)(0=u l ，对0u v ≠，令∞=)(v l ，}{00u S =，0=i 。 (ii) 对每个i S v ∈（i i S V S \=），用 )}()(),({min uv w u l v l i S u +∈ 代替)(v l 。计算)}({min v l i S v ∈，把达到这个最小值的一个顶点记为1+i u ，令}{11++=i i i u S S 。 (iii). 若1||-=V i ，停止；若1||- Floyd算法Matlab程序第一种: %floyd.m %采用floyd算法计算图a中每对顶点最短路 %d是矩离矩阵 %r是路由矩阵 function ,d,r,=floyd(a) n=size(a,1); d=a; for i=1:n for j=1:n r(i,j)=j; end end r for k=1:n for i=1:n for j=1:n if d(i,k)+d(k,j) end k d r end 第二种: %Floyd算法 %解决最短路径问题，是用来调用的函数头文件 %[D,path]=floyd(a) %输入参数a是求图的带权邻接矩阵，D(i,j)表示i到j的最短距 离,path(i,j)i,j之间最短路径上顶点i的后继点 %[D,path,min1,path1]=floyd(a,i,j) %输入参数a是所求图的带权邻接矩阵，i,j起点终点,min1表示i与j最短距离，path1为最短路径function [D,path,min1,path1]=floyd(a,start,terminal) D=a;n=size(D,1);path=zeros(n,n); for i=1:n for j=1:n if D(i,j)~=inf path(i,j)=j; end end end for k=1:n for i=1:n for j=1:n if D(i,k)+D(k,j) 硕士生考查课程考试试卷 考试科目：MATLAB教程 考生姓名：考生学号： 学院：专业： 考生成绩： 任课老师(签名) 考试日期：20 年月日午时至时 《MATLAB教程》试题： A、利用MATLAB设计遗传算法程序，寻找下图11个端点的最短路径，其中没有连接的端点表示没有路径。要求设计遗传算法对该问题求解。 a c d e f h i k 1 2 1 6 8 3 1 7 9 4 6 7 2 9 4 2 1 1 B、设计遗传算法求解f(x)极小值，具体表达式如下： 要求必须使用m函数方式设计程序。 C、利用MATLAB编程实现：三名商人各带一个随从乘船渡河，一只小船只能容纳二人，由他们自己划行，随从们密约，在河的任一岸，一旦随从的人数比商人多，就杀人越货，但是如何乘船渡河的大权掌握在商人手中，商人们怎样才能安全渡河？ D、结合自己的研究方向选择合适的问题，利用MATLAB进行实验。 以上四题任选一题进行实验，并写出实验报告。 选择题目： A 一、问题分析（10分） 1 2 3 4 5 6 8 9 10 11 1 2 1 6 8 3 1 7 9 4 6 7 2 9 4 2 1 1 如图如示，将节点编号，依次为 1.2.3.4.5.6.7.8.9.10.11，由图论知识，则可写出其带权邻接矩阵为： 0 2 8 1 500 500 500 500 500 500 500 2 0 6 500 1 500 500 500 500 500 500 8 6 0 7 500 1 500 500 500 500 500 1 500 7 0 500 500 9 500 500 500 500 500 1 500 500 0 3 500 2 500 500 500 500 500 1 500 3 0 4 500 6 500 500 500 500 500 9 500 4 0 500 500 1 500 500 500 500 500 2 500 500 0 7 500 9 500 500 500 500 500 6 500 7 0 1 2 500 500 500 500 500 500 1 500 1 0 4 500 500 500 500 500 500 500 9 2 4 0 注：为避免计算时无穷大数吃掉小数，此处为令inf=500。 问题要求求出任意两点间的最短路径，Floyd算法采用的是在两点间尝试插入顶点，比较距离长短的方法。我思考后认为，用遗传算法很难找到一个可以统一表示最短路径的函数，但是可以对每一对点分别计算，然后加入for循环，可将相互之间的所有情况解出。观察本题可发现，所有节点都是可双向行走，则可只计算i到j的路径与距离，然后将矩阵按主对角线翻折即可得到全部数据。二、实验原理与数学模型（20分） 实现原理为遗传算法原理： 按所选择的适应度函数并通过遗传中的复制、交叉及变异对个体进行筛选，使得适应度高的个体被保留下来，组成新的群体，新的群体既继承了上一代的信息，又优于上一代。这样周而复始，群体中个体适应度不断提高，直到满足一定的条件。 数学模型如下： 设图由非空点集合和边集合组成，其中 又设的值为，故可表示为一个三元组 则求最短路径的数学模型可以描述为： 算法描述： 输入图G，源点v0，输出源点到各点的最短距离D 中间变量v0保存当前已经处理到的顶点集合，v1保存剩余的集合 1.初始化v1,D 2.计算v0到v1各点的最短距离，保存到D for each i in v0;D(j)=min[D(j),G(v0(1),i)+G(i,j)] ,where j in v1 3.将D中最小的那一项加入到v0，并且从v1删除这一项。 4.转到2，直到v0包含所有顶点。 %dijsk最短路径算法 clear,clc G=[ inf inf 10 inf 30 100; inf inf 5 inf inf inf; inf 5 inf 50 inf inf; inf inf inf inf inf 10; inf inf inf 20 inf 60; inf inf inf inf inf inf; ]; %邻接矩阵 N=size(G,1); %顶点数 v0=1; %源点 v1=ones(1,N); %除去原点后的集合 v1(v0)=0; %计算和源点最近的点 D=G(v0,:); while 1 D2=D; for i=1:N if v1(i)==0 D2(i)=inf; end end D2 [Dmin id]=min(D2); if isinf(Dmin),error,end v0=[v0 id] %将最近的点加入v0集合，并从v1集合中删除 v1(id)=0; if size(v0,2)==N,break;end %计算v0（1）到v1各点的最近距离 fprintf('计算v0（1）到v1各点的最近距离\n');v0,v1 id=0; for j=1:N %计算到j的最近距离 if v1(j) TRANSPOWORLD 2009 No.12 (Jun) 104前言 在现实生活中，我们经常遇到最短路问题，例如寻找两点之间总长度最短或者费用最低的路径。在运输、物流、设施选址以及人员调度问题中，最短路径是很常见的问题。解决最短路问题的方法有很多，例如迪杰斯特拉算法、福特算法。在这里我们介绍基于遗传算法的最短路径问题的解决方案。 模型 遗传算法基本模型 遗传算法是模仿生物进化过程，针对复杂问题开发出来的非常有效的方 基于遗传算法的最短路径问题及其MATLAB 实现 文/张书源 郭 聪 法。根据生物进化过程中的选择机制，在问题的解空间中进行选择，实现“物竞天择，适者生存”。在遗传算法中，一条染色体代表问题的一个可行解，该染色体的适应值即为对应于该可行解的函数值。一般来说，遗传算法包括以下几个主要组成部分。编码 即将问题的解表示成一个编码串（染色体），每一染色体对应问题的一 个解。遗传过程 对染色体进行操作，以产生新的染色体，通常有不同染色体之间的交叉 操作以及一条染色体的变异操作。评价与选择 对每条染色体计算其适应值，用以评价染色体的优劣，从而从父代和子代中选择较优的染色体，进入下一代的繁殖。 初试种群的创建方法 其作为问题可行解的集合。初始种群中染色体个数称为种群规模。 遗传算法的流程图如图1所示。算法过程如下: 第一步初始化种群p(t)；第二步对种群进行评价； 第三步利用交叉和变异重组p(t)以产生c(t) 第四步评价c(t)，从p(t)和c(t)选择出p(t+1)，令t=t+1；若达到繁殖代数，转第五步；否则，回第四步； 第五步返回结果。 问题描述 在图2所示的算例中，我们要找到从节点①到节点⑨的最短路径。基于优先权的编码方式 例如，一条可能的染色体如表1。路径生长 路径生长即为根据一条染色体来得到其对应的一条路。在表1的例子中，路径生长的过程如下： 初试路径上只有节点①； 与①相连且不在当前路径上的节点有②和③，其中节点③的权较大，为6，将节点③加入当前路径，当前路径变为：①—③； 与③相连且不在当前路径上的节 点有④和⑤，其中节点⑤的权较大，为 图2 C OLUMNS 特别企划 小世界网络简介及MATLAB建模 1.简介 小世界网络存在于数学、物理学和社会学中，是一种数学图的模型。在这种图中大部份的结点不与彼此邻接，但大部份结点可以通过任一其它节点经少数几步就可以产生联系。若将一个小世界网络中的点代表一个人，而联机代表人与人之间是相互认识的，则这小世界网络可以反映陌生人通过彼此共同认识的人而起来产生联系关系的小世界现象。 在日常生活中，有时你会发现，某些你觉得与你隔得很“遥远”的人，其实与你“很近”。小世界网络就是对这种现象的数学描述。用数学中图论的语言来说，小世界网络就是一个由大量顶点构成的图，其中任意两点之间的平均路径长度比顶点数量小得多。除了社会人际网络以外，小世界网络的例子在生物学、物理学、计算机科学等领域也有出现。许多经验中的图可以用小世界网络来作为模型。因特网、公路交通网、神经网络都呈现小世界网络的特征。 小世界网络最早是由邓肯·瓦茨（Duncan Watts）和斯蒂文·斯特罗加茨（Steven Strogatz）在1998年引进的，将高聚合系数和低平均路径长度作为特征，提出了一种新的网络模型，一般就称作瓦茨-斯特罗加茨模型（WS模型），这也是最典型的小世界网络的模型。 由于WS小世界模型构造算法中的随机化过程有可能破坏网络的连通性，纽曼(Newman)和瓦茨(Watts)提出了NW小世界网络模型，该模型是通过用“随机化加边”模式来取代WS小世界网络模型构造中的“随机化重连”。 在考虑网络特征的时候，使用两个特征来衡量网络：特征路径长度和聚合系数。 特征路径长度（characteristic path length）：在网络中，任选两个节点，连同这两个节点的最少边数，定义为这两个节点的路径长度，网络中所有节点对的路径长度的平均值，定义为网络的特征路径长度。这是网络的全局特征。 聚合系数(clustering coefficient)：假设某个节点有k个边，则这k条边连接的节点之间最多可能存在的边的个数为k(k-1)/2，用实际存在的边数除以最多可能存在的边数得到的分数值，定义为这个节点的聚合系数。所有节点的聚合系数的均值定义为网络的聚合系数。聚合系数是网络的局部特征，反映了相邻两个人之间朋友圈子的重合度，即该节点的朋友之间也是朋友的程度。 我们可以发现规则网络具有很高的聚合系数，大世界（large world，意思是特征路径长度很大），其特征路径长度随着n(网络中节点的数量)线性增长，而随机网络聚合系数很小，小世界（small world，意思是特征路径长度小），其特征路径长度随着log(n)增长中说明，在从规则网络向随机网络转换的过程中，实际上特征路径长度和聚合系数都会下降，到变成随机网络的时候，减少到最少。但这并不是说大的聚合系数一定伴随着大的路径长度，而小的路径长度伴随着小的聚合系数，小世界网络就具有大的聚合系数，而特征路径长度很小。试验表明，少量的short cut的建立能够迅速减少特征路径长度，而聚合系数变化却不大，因为某一个short cut的建立，不仅影响到所连接的节点的特征路径长度，而且影响到他们邻居的路径长度，而对整个网络的聚合系数影响不大。这样，少量的short cut的建立就能使整个网络不知不觉地变成小世界网络。 实际的社会、生态、等网络都是小世界网络，在这样的系统里，信息传递速度快，并且少量改变几个连接，就可以剧烈地改变网络的性能，如对已存在的网络进行调整， 最短路径法射线追踪的MATLAB 实现 李志辉 刘争平 （西南交通大学土木工程学院 成都 610031） 摘 要：本文探讨了在MA TLAB 环境中实现最短路径射线追踪的方法和步骤，并通过数值模拟演示了所编程序在射线追踪正演计算中的应用。 关键词：最短路径法 射线追踪 MATLAB 数值模拟 利用地震初至波确定近地表介质结构，在矿产资源的勘探开发及工程建设中有重要作用。地震射线追踪方法是研究地震波传播的有效工具，目前常用的方法主要有有限差分解程函方程法和最小路径法。最短路径方法起源于网络理论，首次由Nakanishi 和Yamaguchi 应用域地震射线追踪中。Moser 以及Klimes 和Kvasnicha 对最短路径方法进行了详细研究。通过科技人员的不断研究，最短路径方法目前已发展较为成熟，其基本算法的计算程序也较为固定。 被称作是第四代计算机语言的MA TLAB 语言，利用其丰富的函数资源把编程人员从繁琐的程序代码中解放出来。MA TLAB 用更直观的、符合人们思维习惯的代码，为用户提供了直观、简洁的程序开发环境。本文介绍运用Matlab 实现最短路径法的方法和步骤，便于科研院校教学中讲授、演示和理解最短路径方法及其应用。 1 最短路径法射线追踪方法原理 最短路径法的基础是Fermat 原理及图论中的最短路径理论。其基本思路是，对实际介质进行离散化，将这个介质剖分成一系列小单元，在单元边界上设置若干节点，并将彼此向量的节点相连构成一个网络。网络中，速度场分布在离散的节点上。相邻节点之间的旅行时为他们之间欧氏距离与其平均慢度之积。将波阵面看成式由有限个离散点次级源组成，对于某个次级源（即某个网格节点），选取与其所有相邻的点（邻域点）组成计算网格点；由一个源点出发，计算出从源点到计算网格点的透射走时、射线路径、和射线长度；然后把除震源之外的所有网格点相继当作次级源，选取该节点相应的计算网格点，计算出从次级源点到计算网格点的透射走时、射线路径、和射线长度；将每次计算出来的走时加上从震源到次级源的走时，作为震源点到该网格节点的走时，记录下相应的射线路径位置及射线长度。 图1 离散化模型（星点表示震源或次级震源，空心点为对应计算网格点） 根据Fermat 原理逐步计算最小走时及射线方向。设Ω为已知走时点q 的集合，p 为与其相邻的未知走时点，tq 分别和p 点的最小走时，tqp 为q 至p 最小走时。r 为p 的次级源位置，则 )}(min :{qp q P t t t q r q +==Ω ∈ 根据Huygens 原理，q 只需遍历Q 的边界（即波前点），当所有波前邻点的最小走时都求出时，这些点又成为新的波前点。应用网络理论中的最短路径算法，可以同时求出从震源点传至所有节点之间的连线近似地震射线路径。 2 最短路径法射线追踪基本算法步骤 把网格上的所有节点分成集合p 和q ，p 为已知最小旅行时的结点总数集合，q 为未知最小旅行时的节点的集合。若节点总数为n ，经过n 次迭代后可为求出所有节点的最小旅行时。过程如下： 1) 初始时 q 集合包含所有节点，除震源s 的旅行时已知为ts ＝0外，其余所有节点的旅行时均为ti ＝（i 属于Q 但不 等于s ）。P 集合为空集。 2) 在Q 中找一个旅行时最小的节点i ，它的旅行时为ti ； 3) 确定与节点i 相连的所有节点的集合V ； 4) 求节点j （j 属于V 且j 不属于P ）与节点i 连线的旅行时dtij ； 5) 求节点j （）的新旅行时tj （取原有旅行时tj 与tj ＋dtij 的最小值）； 6) 将i 点从Q 集合转到P 集合； 7) 若P 集合中的节点个数小于总节点数N ，转2，否则结束旅行时追踪； 8) 从接收点开始倒推出各道从源点道接收点的射线路径，只要每个节点记下使它形成最小旅行时的前一个节点号， 实验四：Floyd 算法 一、实验目的 利用MATLAB 实现Floyd 算法，可对输入的邻接距离矩阵计算图中任意两点间的最短距离矩阵和路由矩阵，且能查询任意两点间的最短距离和路由。 二、实验原理 Floyd 算法适用于求解网络中的任意两点间的最短路径：通过图的权值矩阵求出任意两点间的最短距离矩阵和路由矩阵。优点是容易理解，可以算出任意两个节点之间最短距离的算法，且程序容易实现，缺点是复杂度达到，不适合计算大量数据。 Floyd 算法可描述如下： 给定图G 及其边(i , j )的权w i, j (1≤i≤n ,1≤j≤n) F0：初始化距离矩阵W(0)和路由矩阵R(0)。其中： F1：已求得W(k-1)和R(k-1)，依据下面的迭代求W(k)和R(k) F2：若k≤n，重复F1；若k>n，终止。 三、实验内容 1、用MATLAB 仿真工具实现Floyd 算法：给定图G 及其边(i , j )的权 w i , j (1≤i≤n ,1≤j≤n) ，求出其各个端点之间的最小距离以及路由。 （1）尽可能用M 函数分别实现算法的关键部分，用M 脚本来进行算法结 果验证； （2）分别用以下两个初始距离矩阵表示的图进行算法验证： 分别求出W(7)和R(7)。 2、根据最短路由矩阵查询任意两点间的最短距离和路由 （1）最短距离可以从最短距离矩阵的ω(i,j)中直接得出； （2）相应的路由则可以通过在路由矩阵中查找得出。由于该程序中使用的是前向矩阵，因此在查找的过程中，路由矩阵中r(i,j)对应的值为Vi 到Vj 路由上的下一个端点，这样再代入r(r(i,j),j)，可得到下下个端点，由此不断循环下去，即可找到最终的路由。 （3）对图1，分别以端点对V4 和V6, V3 和V4 为例，求其最短距离和路由；对图2，分别以端点对V1 和V7，V3 和V5，V1 和V6 为例，求其最短距离和路由。 3、输入一邻接权值矩阵，求解最短距离和路由矩阵，及某些点间的最短路径。 四、采用的语言 MatLab 源代码： 【func1.m】 function [w r] = func1(w) n=length(w); x = w; r = zeros(n,1);%路由矩阵的初始化 for i=1:1:n for j=1:1:n if x(i,j)==inf r(i,j)=0; else r(i,j)=j; end, end end; %迭代求出k次w值 for k=1:n a=w; s = w; for i=1:n 目录 摘要 (1) 1 理论知识 (2) 1.1基尔霍夫定律 (2) 1.2结点电压法 (2) 2 阻抗匹配网络的计算 (3) 2.1原理分析 (3) 2.2 建模 (4) 2.3应用MATLAB对上面的题目编程 (5) 2.4 绘图 (6) 3 simulink程序仿真 (8) 3.1电路图及仿真效果 (8) 3.2仿真过程中发现的问题 (9) 4 结果对比分析 (10) 5 心得体会 (11) 参考文献 (12) 摘要 做为一名自动化专业的学生，掌握基本的电路知识是非常重要的。但是在掌握基本的知识点的时候，我们也需要掌握一些解决电路方面的“诀窍”，比如某些软件。本文就以电路中的一些基本知识点引入这些软件在解决电路问题中的一些具体应用。而且本文是以Matlab为例，说明如何运用Matlab来进行电路的求解和仿真。 在求解和仿真的过程中，我们可以发现应用这些软件可以让非常复杂的电路的分析、计算编的非常简单，是一个非常实用、有效的工具。 关键词：电路；Matlab；仿真； 1 理论知识 1.1基尔霍夫定律 基尔霍夫定律包括基尔霍夫电流定律（KCL）和基尔霍夫电压定律（KVL）。 基尔霍夫电流定律（KCL）：在集总电路中，任何时候，对任意结点，所有流出结点的支路电流的代数和恒为零。电流的“代数和”是根据电流是流出结点还是流入结点判断的。若流出节点的电流前面取“+”号，则流入结点的电流前面取“-”号；电流是流出结点还是流入结点，均根据电流的参考方向判断。所以对任一结点都有 Σi=0； 基尔霍夫电压定律（KVL）: 在集总电路中，任何时候，对任意回路，所有支路电压的代数和恒为零。在应用时，需要任意指定一个回路的绕行方向，凡是支路电压的参考方向与回路的绕行方向一致者，该电压前面取“+”号；支路电压参考方向与回路绕行方向相反者，前面取“-”。最后，对任一回路都有 Σu=0； 1.2结点电压法 定义：结点电压是在为电路任选一个结点作为参考点（此点通常编号为“0”），并令其电位为零后,其余结点对该参考点的电位。并根据KCL写出方程，求出每个结点的电压。 在电路中任意选择某一结点为参考结点，其他结点为独立结点，这些结点与次参考结点之间的电压称为结点电压，结点电压的参考极性是以参考结点为负，其余独立结点为正。由于任意支路都连接在两个节点上，根据KVL，不难断定支路电压就是两个结点电压表示。在具有n个结点电压的共（n-1）个独立结点的KCL方程，就得到变量为（n-1）个独立方程，称为结点电压方程，最后由这些方程解出结点电压，从而求出所需的电压、电流。这就是结点电压法。 精心整理 图论算法matlab实现 求最小费用最大流算法的 MATLAB 程序代码如下： n=5;C=[0 15 16 0 0 0 0 0 13 14 for while for for(i=1:n)for(j=1:n)if(C(i,j)>0&f(i,j)==0)a(i,j)=b(i,j); elseif(C(i,j)>0&f(i,j)==C(i,j))a(j,i)=-b(i,j); elseif(C(i,j)>0)a(i,j)=b(i,j);a(j,i)=-b(i,j);end;end;end for(i=2:n)p(i)=Inf;s(i)=i;end %用Ford 算法求最短路, 赋初值 for(k=1:n)pd=1; %求有向赋权图中vs 到vt 的最短路 for(i=2:n)for(j=1:n)if(p(i)>p(j)+a(j,i))p(i)=p(j)+a(j,i);s(i)=j;pd=0;end ;end;end if(pd)break;end;end %求最短路的Ford 算法结束 if(p(n)==Inf)break;end %不存在vs 到vt 的最短路, 算法终止. 注意在求最小费用最大流时构造有 while if elseif if if pd=0; 值 t=n; if elseif if(s(t)==1)break;end %当t 的标号为vs 时, 终止调整过程 t=s(t);end if(pd)break;end%如果最大流量达到预定的流量值 wf=0; for(j=1:n)wf=wf+f(1,j);end;end %计算最大流量 zwf=0;for(i=1:n)for(j=1:n)zwf=zwf+b(i,j)*f(i,j);end;end%计算最小费用 毕业论文 题目：复杂网络及其matlab模拟学院：物理与电子工程学院 专业：物理学 毕业年限：2015 学生姓名： 学号： 指导教师： 复杂网络及其matlab模拟 班级：物理学2班姓名：指导教师： 摘要近年来,关于复杂网络的研究正方兴未艾,1998年Watts和Strogatz 在Nature杂志上发表文章,引入了小世界(Small一World)网络模型。本文对复杂网络的特性还有无标度与小世界网络进行简单介绍，详细介绍各个模型的生成与算法，并用matlab软件进行了模拟。 关键词复杂网络无标度小世界模拟 Abstract In recent years, the research on complex networks of academia is be just unfolding, in particular, the two pioneering work set off an upsurge in the study of complex networks.In 1998 Watts and Strogatz published an article In this paper, the properties of complex networks are scale-free and small world networks are briefly introduced,Generation and algorithm details of each model, and use MATLAB software to simulate. Key word Complex network；Scale free；Small World；Simulation 引言 在人类生存的整个空间甚至宇宙中都存在着大量复杂系统，这些系统可以通过形形色色的网络加以描述。一个典型的网络是由许多节点与连接两个节点之间的一些边组成的，其中节点用来代表真实系统中不同的个体，而边则用来表示个体间的关系，往往是两个节点之间具有某种特定的关系则连一条边，反之则不连边，有边相连的两个节点在网络中被看作是相邻的。例如，神经系统可以看作大量神经细胞通过神经纤维相互连接形成的网络[1]；计算机网络可以看作是自主工作的计算机通过通信介质如光缆、双绞线、同轴电缆等相互连接形成的网络[2],类似的还有电力网络[1]、社会关系网络[1,4]、交通网络等等。数学家和物理学家在研究网络的时候，往往只关心节点之间有没有边相连，至于节点到底在什么位置，边是长还是短，是弯曲还是平直，有没有相交等等都是他们不在意的。在这里， 蚁群算法最短路径通用Matlab程序（附图） function [ROUTES,PL,Tau]=ACASP(G,Tau,K,M,S,E,Alpha,Beta,Rho,Q) %% --------------------------------------------------------------- % ACASP.m % 蚁群算法动态寻路算法 % ChengAihua,PLA Information Engineering University,ZhengZhou,China % Email:aihuacheng@https://www.doczj.com/doc/5619010032.html, % All rights reserved %% --------------------------------------------------------------- % 输入参数列表 % G 地形图为01矩阵，如果为1表示障碍物 % Tau 初始信息素矩阵（认为前面的觅食活动中有残留的信息素） % K 迭代次数（指蚂蚁出动多少波） % M 蚂蚁个数（每一波蚂蚁有多少个） % S 起始点（最短路径的起始点） % E 终止点（最短路径的目的点） % Alpha 表征信息素重要程度的参数 % Beta 表征启发式因子重要程度的参数 % Rho 信息素蒸发系数 % Q 信息素增加强度系数 % % 输出参数列表 % ROUTES 每一代的每一只蚂蚁的爬行路线 % PL 每一代的每一只蚂蚁的爬行路线长度 % Tau 输出动态修正过的信息素 %% --------------------变量初始化---------------------------------- %load D=G2D(G); N=size(D,1);%N表示问题的规模（象素个数） MM=size(G,1); a=1;%小方格象素的边长 Ex=a*(mod(E,MM)-0.5);%终止点横坐标 if Ex==-0.5 Ex=MM-0.5; end Ey=a*(MM+0.5-ceil(E/MM));%终止点纵坐标 Eta=zeros(1,N);%启发式信息，取为至目标点的直线距离的倒数 %下面构造启发式信息矩阵 for i=1:N if ix==-0.5 一、实验目的 利用MATLAB实现Floyd算法，可对输入的邻接距离矩阵计算图中任意两点间的最短距离矩阵和路由矩阵，且能查询任意两点间的最短距离和路由。 二、实验原理 Floyd 算法适用于求解网络中的任意两点间的最短路径：通过图的权值矩阵求出任意两点间的最短距离矩阵和路由矩阵。优点是容易理解，可以算出任意两个 节点之间最短距离的算法，且程序容易实现，缺点是复杂度达到，不适合计算大量数据。 Floyd 算法可描述如下： 给定图G及其边(i , j ) 的权w, j (1 < i < n ,1 图论算法及其MATLAB程序代码 求赋权图G = (V, E , F )中任意两点间的最短路的Warshall-Floyd算法： 设A = (a ij )n×n为赋权图G = (V, E , F )的矩阵, 当v i v j∈E时a ij= F (v i v j), 否则取a ii=0, a ij = +∞(i≠j ), d ij表示从v i到v j点的距离, r ij表示从v i到v j点的最短路中一个点的编号. ①赋初值. 对所有i, j, d ij = a ij, r ij = j. k = 1. 转向② ②更新d ij, r ij . 对所有i, j, 若d ik + d k j＜d ij, 则令d ij = d ik + d k j, r ij = k, 转向③. ③终止判断. 若d ii＜0, 则存在一条含有顶点v i的负回路, 终止; 或者k = n终止; 否则令k = k + 1, 转向②. 最短路线可由r ij得到. 例1求图6-4中任意两点间的最短路. 图6-4 解：用Warshall-Floyd算法, MA TLAB程序代码如下： n=8;A=[0 2 8 1 Inf Inf Inf Inf 2 0 6 Inf 1 Inf Inf Inf 8 6 0 7 5 1 2 Inf 1 Inf 7 0 Inf Inf 9 Inf Inf 1 5 Inf 0 3 Inf 8 Inf Inf 1 Inf 3 0 4 6 Inf Inf 2 9 Inf 4 0 3 Inf Inf Inf Inf 8 6 3 0]; % MATLAB中, Inf表示∞ D=A; %赋初值 for(i=1:n)for(j=1:n)R(i,j)=j;end;end%赋路径初值 for(k=1:n)for(i=1:n)for(j=1:n)if(D(i,k)+D(k,j) Dijkstra 算法Matlab 实现。 %求一个点到其他各点的最短路径 function [min,path]=dijkstra(w,start,terminal) %W 是邻接矩阵 %start 是起始点 %terminal 是终止点 %min 是最短路径长度 %path 是最短路径 n=size(w,1); label(start)=0; f(start)=start; for i=1:n if i~=start label(i)=inf; end end s(1)=start; u=start; while length(s) 计算机仿真期末作业 姓名：吴隐奎 班级：04601 学号：041751 日期：2007-6-15 题目：Floyd 算法实现和分析 内容：用MATLAB 仿真工具实现Floyd 算法，求任意两端间的最短路径。 要求：尽可能用M 函数分别实现算法的关键部分，用M 脚本来进行算法结果验证；分别用以下两个图（用初始距离矩阵表示）进行算法验证： 图一：(0)0 100 100 1.2 9.2 100 0.5100 0 100 5 100 3.1 2100 100 0 100 100 4 1.51.2 5 100 0 6.7 100 1009.2 100 100 6.7 0 15.6 100100 3.1 4 100 15.6 0 1000.5 2 1.5 100 100 100 0]W ??????????=???????????? 图二：(0) 0 0.5 2 1.5 100 100 1000.5 0 100 100 1.2 9.2 1002 100 0 100 5 100 3.11.5 100 100 0 100 100 4100 1.2 5 100 0 6.7 100100 9.2 100 100 6.7 0 15.6100 100 3.1 4 100 15.6 0W ??????????=???????????? 算法：给定图G 及其边(,)i j 的权,(1,1)i j w i n j n ≤≤≤ ≤ F0：初始化距离矩阵(0)W 和路由矩阵(0)R 。其中： (0)0ij ij ij ij w e E w e E i j ∈??=∞???=? 若（有边） 若（无边） 若(对角线元素) (0)(0)w 0,ij ij j r ?≠∞=?? 若 其它 F1：已求得(-1)k W 和(-1)k R ，依据下面的迭代求()k W 和()k R ()(1)(1)(-1),,,,min(,)k k k k i j i j i k k j w w w w --=+ 课程设计任务书 学生姓名：叶枫专业班级：通信zy1201班指导教师：姜宁工作单位：信息工程学院 题目: 利用MATLAB仿真软件系统进行图像的数据分析初始条件： 1.MATLAB软件。 2.数字信号处理与图像处理基础知识。 要求完成的主要任务: 读取图像并求出图像的最大值、最小值、均值、中值、和、标准差、两图像的协方差、相关系数等。 课程设计的目的： 1．理论目的 课程设计的目的之一是为了巩固课堂理论学习，并能用所学理论知识正确分析信号处理的基本问题和解释信号处理的基本现象。 2．实践目的 课程设计的目的之二是通过设计具体的图像信号变换掌握图像和信号处理的方法和步骤。 时间安排： 指导教师签名：年月日 系主任（或责任教师）签名：年月日 目录 摘要 (3) Abstract (4) 1.Matlab及课程设计所用函数简介 (5) 1.1Matlab简介 (5) 1.2课程设计所用函数简介 (6) 2.数据采集 (9) 2.1 MATLAB的读取方法 (9) 3图像数据统计处理 (13) 3.1 图像数据处理原理 (13) 3.2各像素点中最大值的获取 (14) 3.3各像素点中最小值的获取 (14) 3.4各像素点值的均值的获取 (15) 3.5各像素点值的中值的获取 (16) 3.6各像素点值的和的获取 (17) 3.7各像素点值的标准差的获取 (18) 3.8各像素点值的方差的获取 (19) 3.9两图中各像素点值的协方差的获取 (20) 3.10两图的相对系数的获取 (20) 4.心得体会 (22) 参考文献 (23) 摘要 MATLAB软件是矩阵实验室的简称，是美国MathWorks公司出品的商业数学软件，可用于算法开发、数据可视化、数据分析以及数值计算的高级技术计算语言和交互式环境，广泛用于数字信号分析，系统识别，时序分析与建模，神经网络、动态仿真等方面有着广泛的应用。 MATLAB因具有强大的图形处理功能、符号运算功能和数值计算功能，而被广泛应用。而且随着信息时代和数字世界的到来，数字信号处理也已成为当今一门极其重要的学科和技术领域。目前数字信号处理在通信、语音、图像、自动控制、雷达、军事、航空航天、医疗和家用电器等众多领域得到了广泛的应用。 本次课程设计利用MATLAB软件进行图像的数据分析，包括读取图像并求出图像的最大值、最小值、均值、中值、和、标准差、两图像的协方差、相关系数等。 关键词：MATLAB，数字信号处理，图像数据分析最短路径的Dijkstra算法及Matlab程序
Floyd算法Matlab程序
MATLAB实验报告-遗传算法解最短路径以及函数最小值问题
最短路径算法_matlab程序[1]
基于遗传算法的最短路径问题及其MATLAB实现
小世界网络简介及MATLAB建模
最短路径法射线追踪的MATLAB实现
Floyd算法_计算最短距离矩阵和路由矩阵_查询最短距离和路由_matlab实验报告
matlab在阻抗匹配网络的应用
matlab图论程序算法大全
复杂网络及其matlab模拟
蚁群算法最短路径通用Matlab程序(附图)
Floyd算法_计算最短距离矩阵和路由矩阵_查询最短距离和路由_matlab实验报告
图论算法及其MATLAB程序代码
Dijkstra、Floyd算法Matlab_Lingo实现
最短路径matlab计算机仿真
利用MATLAB仿真软件系统进行图像的数据分析
相关主题
文本预览