最短路径matlab源代码（最短路径例题图解matlab）

今天给各位分享最短路径matlab源代码的知识，其中也会对最短路径例题图解matlab进行解释，如果能碰巧解决你现在面临的问题，别忘了关注本站，现在开始吧！

本文目录一览：

• 1、matlab求最短路径
• 2、求利用matlab求从A到O的最短路径的程序代码~~~
• 3、matlab 最优路径 代码
• 4、用Dijkstra算法求最短路径的MATLAB程序
• 5、MATLAB问题——关于“最短路径”

matlab求最短路径

如何用matlab求最短路径？

运行并分析了题主给出的代码，a=a+((a==0)-eye(n))*M 这个代码出错，其出错的原因是a和eye(n)的矩阵维度不一致。

因为题主一开始，就出现了误解，对a定义为zeros(n)，而实际a是二维矩阵，应该为

a=zeros(n,n)

同理，path=zeros(n) 也是错误的，应该为

path=zeros(n,n)

附带说明，用matlab求最短路径，可以用下列函数就可以完成，即

graph() %对象表示无向图，无向图具有连接相应节点的无向边。

shortestpath() %计算从源节点 s 处开始到目标节点 t 处结束的最短路径。

plot() %绘制一个有向图

下面为运行后的一个图例。

求利用matlab求从A到O的最短路径的程序代码~~~

function R=main_Dj()

clc;clear

G=[1 2 5;1 4 1;2 3 1;2 4 6;2 5 5.8;2 6 5.7;2 7 5.6;3 7 2; 3 11 1.5; 3 12 4;...

    4 5 0.5;4 8 3; 5 6 1;5 9 3;6 7 0.6;6 10 2.5; 7 11 2.7;8 9 1;8 12 6;...

    9 10 1.5;9 12 5;10 11 0.5;10 12 4;11 12 3];

opt=0;

route=sroute(G,opt);

R=[];

r=route(3,end);

R=[r,R];

while r~=1

  r=route(3,r);

  R=[r,R];

end

R=char(R+64);

R=[R,'O'];

end

function route=sroute(G,opt)

% 求图的最短路的Dijkstra算法，规定1是起点

% G是给定图的邻接矩阵或弧表矩阵，程序能够自动识别

% 当opt=0（或缺省）时求无向图的最短路，opt=1时求有向图的最短路

% d——标记最短距离 

% route是一个矩阵，第一行标记顶点，第2行标记1到该点的最短距离，

% 第3行标记最短路上该点的先驱顶点

if (nargin==1) opt=0; end

while 1      % 此循环自动识别或由弧表矩阵生成邻接矩阵

   if G(1,1)==0

      A=G;

      n=size(A,1);

      M=sum(sum(A));break

   else

      e=G;

      n=max([e(:,1);e(:,2)]);          % 顶点数

      m=size(e,1);                     % 边数

      M=sum(e(:,3));                   % 代表无穷大

      A=M*ones(n,n);

      for k=1:m

          A(e(k,1),e(k,2))=e(k,3);  

          if opt==0 

               A(e(k,2),e(k,1))=e(k,3); % 形成无向图的邻接矩阵

          end         

      end

      A=A-M*eye(n);                      % 形成图的邻接矩阵      

   end

   break

end

pb(1:length(A))=0;pb(1)=1;               % 永久标号点记为1

index1=1;                                % 依次记录永久标号顶点

index2=ones(1,length(A));                % 标记最短路上各点的先驱顶点

d(1:length(A))=M;d(1)=0;                 % 标记距离

temp=1;                                  % 标记最近一个永久标号点

while sum(pb)length(A)

   tb=find(pb==0);                       % 找出临时标号点

   d(tb)=min(d(tb),d(temp)+A(temp,tb));  % 更新距离

   tmpb=find(d(tb)==min(d(tb)));         % 确定新最小距离点

   temp=tb(tmpb(1));                     % 其中之一记为新永久标号点

   pb(temp)=1;                           % 增加新永久标号点

   index1=[index1,temp];                 % 记录新永久标号点

   index=index1(find(d(index1)==d(temp)-A(index1,temp)')); % 确定前驱顶点

   if length(index)=2                   % 前驱顶点多于1个时取第一个

      index=index(1);

   end

   index2(temp)=index;                   % 记录前驱顶点

end

route=[1:n; d; index2];

end

运行结果

R =

ADEFJKO

代码自己看，不解释，也别叫我解释了，很麻烦的。

matlab 最优路径 代码

问题本身是个np难问题，随着点数n的增加，计算量呈n！递增

对于n=10以内的计算，可以用穷举法得到

n再增大，计算的时间就会很长

求全局最优解就没有快速的算法

只能用优化的方法求局部最优解

对于n较小的情况可以用穷举法

因为从某点出发在回到该点的路径是循环的

所以具体从哪点出发得到的解是一样的

而走的顺序是顺时针或者逆时针路程也是一样的

程序如下

n=8;

x=rand(n,1);

y=rand(n,1); %随机n个点坐标

d=squareform(pdist([x,y]));%统计坐标之间的距离

p=perms(2:n); %穷举所有可能路径，1固定为起点

m=factorial(n-1);

l=zeros(m,1); %记录路径长度的矩阵

for ii=1:m

ind=sub2ind([n,n],[1,p(ii,:)],[p(ii,:),1]); %获得路径

l(ii)=sum(d(ind));%计算路径长度

end

[minl in]=min(l); %找出最短路径

a=full(sparse([1,p(in,:)],[p(in,:),1],1,n,n)); %最短路径的连接矩阵

gplot(a,[x y],'-o'); %画最短路径图

axis equal

title(['最短路径长度:' num2str(minl)]);

程序利用随机数，随机生成n个点的x，y坐标

然后统计个点相互中间的距离矩阵d

固定第一点为出发点，利用排列穷举了所有可能路径

找出最短的路径，使用邻接矩阵a表示

最后a是一个nxn的矩阵，里面有n个1，每行只有1个1，每列也只有1个1

其余位置为0

用Dijkstra算法求最短路径的MATLAB程序

你对图论的知识有了解吧~W是关联矩阵，s和t分别是起始点和终止节点的序号。返回的d为最短的加权路径长度,p为最优路径节点的序号向量。注意，这里W矩阵为0的点权值已经自动设为无穷大了。请参考《高等应用数学问题的 MATLAB一书》。我吧程序赋给你。

你做一个M函数用吧。

function [d,path]=dijkstra(W,s,t)

[n,m]=size(W);ix=(W==0);W(ix)=inf;

if n~=m,error('Square W required');end

visited(1:n)=0; dist(1:n)=inf;parent(1:n)=0;dist(s)=0;d=inf;

for i=1:(n-1),%求出每个节点与起始点的关系

ix=(visited==0);vec(1:n)=inf;vec(ix)=dist(ix);

[a,u]=min(vec);visited(u)=1;

for v=1:n,if (W(u,v)+dist(u)dist(v)),

dist(v)=dist(u)+W(u,v);parent(v)=u;

end;end;end

if parent(t)~=0,path=t;d=dist(t);%回溯最短路径

while t~=s,p=parent(t);path=[p path];t=p;end;

end;

希望对你有用

是否可以解决您的问题？

MATLAB问题——关于“最短路径”

可以用生物信息工具箱（Bioinformatics Toolbox）的函数graphallshortestpaths求解。

实例如下：

cm = round(rand(13)*80)*0.1;

I = randperm(13^2);

cm(I(1:145))=0;

UG = sparse(tril(cm + cm'));

bg = biograph(UG,arrayfun(@(i){int2str(i)},1:size(cm,1)),'ShowArrows','off','ShowWeights','on');

view(bg)

p = graphallshortestpaths(UG,'directed',false);

num2str(p,'%6g')

其中，前4行用于随机生成一个无向图的数据（懒得输入你图中的数了），第5-6行用于显示图形，最后两行显示各节点之间的最短路径。

以下是某一次随机运行得到的结果：

最短路径：

   0    8  7.5 10.7  8.3 12.4  7.3   10  1.8  6.4  4.7  6.6  6.7

   8    0 14.4  2.7  6.9  6.6  6.9    2  9.3  7.8  3.3  6.2  6.3

 7.5 14.4    0 17.1 15.8  7.8 12.9 16.4  9.3 13.8 12.2 14.1 14.2

10.7  2.7 17.1    0  8.1  9.3  4.2  0.7  9.7  5.1    6  5.8  5.9

 8.3  6.9 15.8  8.1    0    9  3.9  8.8  9.4  4.8  3.6  5.5  5.6

12.4  6.6  7.8  9.3    9    0  5.1  8.6 10.6    6  9.6  6.7  6.8

 7.3  6.9 12.9  4.2  3.9  5.1    0  4.9  5.5  0.9  4.5  1.6  1.7

  10    2 16.4  0.7  8.8  8.6  4.9    0 10.4  5.8  5.3  6.5  6.6

 1.8  9.3  9.3  9.7  9.4 10.6  5.5 10.4    0  4.6    6  4.8  4.9

 6.4  7.8 13.8  5.1  4.8    6  0.9  5.8  4.6    0  5.4  2.5  2.6

 4.7  3.3 12.2    6  3.6  9.6  4.5  5.3    6  5.4    0  2.9    3

 6.6  6.2 14.1  5.8  5.5  6.7  1.6  6.5  4.8  2.5  2.9    0  0.1

 6.7  6.3 14.2  5.9  5.6  6.8  1.7  6.6  4.9  2.6    3  0.1    0

关于最短路径matlab源代码和最短路径例题图解matlab的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。