MATLAB解决最短路径问题代码

2022-09-05 01:01:13 文档大全网 [ 字体：小中大 ] [ 阅读： ]

【#文档大全网# 导语】以下是®文档大全网的小编为您整理的《MATLAB解决最短路径问题代码》，欢迎阅读！
路径,代码,解决,MATLAB,问题
默认是Dijkstra 算法

是有权的, 我想如果把权都赋1的话, 就相当于没权的了参数是带权的稀疏矩阵及结点

看看这两个例子(一个有向一个无向), 或许你能找到你想知道的

% Create a directed graph with 6 nodes and 11 edges

W = [.41 .99 .51 .32 .15 .45 .38 .32 .36 .29 .21]; %这是权

DG = sparse([6 1 2 2 3 4 4 5 5 6 1],[2 6 3 5 4 1 6 3 4 3 5],W) %有权的有向图

h = view(biograph(DG,[],'ShowWeights','on')) %画图, 这个好玩 % Find shortest path from 1 to 6 [dist,path,pred] = graphshortestpath(DG,1,6) %找顶点1到6的最短路径

% Mark the nodes and edges of the shortest path

set(h.Nodes(path),'Color',[1 0.4 0.4]) %上色 edges = getedgesbynodeid(h,get(h.Nodes(path),'ID')); set(edges,'LineColor',[1 0 0]) %上色

set(edges,'LineWidth',1.5) %上色

下面是无向图的例子

% % Solving the previous problem for an undirected graph % UG = tril(DG + DG')

% h = view(biograph(UG,[],'ShowArrows','off','ShowWeights','on')) % % Find the shortest path between node 1 and 6

% [dist,path,pred] = graphshortestpath(UG,1,6,'directed',false) % % Mark the nodes and edges of the shortest path % set(h.Nodes(path),'Color',[1 0.4 0.4])

% fowEdges = getedgesbynodeid(h,get(h.Nodes(path),'ID'));

% revEdges = getedgesbynodeid(h,get(h.Nodes(fliplr(path)),'ID')); % edges = [fowEdges;revEdges]; % set(edges,'LineColor',[1 0 0]) % set(edges,'LineWidth',1.5)

clc;close all; clear; load data; % global quyu; quyu = [2,3];%一片区域

z_jl = lxjl(jdxx,lxxh);%计算路线的距离 z = qyxz(jdxx,quyu,z_jl);

% 根据节点信息，从z中将y区域的节点和路线选出所有点的信息 hzlx(z); %绘制Z的图像

[qypt, nqypt] = ptxzm(xjpt,quyu);

changdu = length(bhxz(jdxx,1:6));%选出x中y区的标号,只是分区域，求长度并绘制它

tt = z(:,[1,2,end])'; k = min(min(tt(1:2,:))); %求两次最小值

t = tt(1:2,:) ;

xsjz = sparse(t(2,:),t(1,:),tt(3,:),changdu,changdu); %产生稀疏矩阵

[dist, path, pred] = zdljxz(xsjz, qypt, k ); %三个原包矩阵通过zdljxz计算得到最短路径 hold on

for j = 1:nqypt

colors = rand(1,3);

%产生随机数并用颜色标记

hzptxc(path{j},jdxx,colors) end hold off axis equal

%把坐标轴单位设为相等

zjd = jdfgd( path, quyu);

function z = lxjl(x, y) %计算路线的距离 [m n] = size(y);

for i = 1:m

yy(i,1:2) = x(y(i,1),2:3); yy(i,3:4) = x(y(i,2),2:3); end

z = sqrt((yy(:,3) - yy(:,1)).^2 + (yy(:,2) - yy(:,4)).^2); y = sort(y'); y = y'; z = [y yy z]; z = sortrows(z);

function [z lz] = ptxz(xjpt,y) pt = xjpt(:,2);

wei = ismember(xjpt(:,1),y); z = pt(wei); lz = length(z);

unction hzptxc(path,jdxx,colors)

n = length(path); % hold on for i = 1:n

hzptjd(jdxx, path{i},colors) end % hold off

unction hzptjd(jdxx,x,colors) % m = length(x); % x = x'; hold on

plot(jdxx(x,2),jdxx(x,3),'o','LineStyle' ,'-' ,... 'Color',colors,'MarkerEdgeColor',colors)

plot(jdxx(x(1),2),jdxx(x(1),3),'*','MarkerFaceColor',colors)

hold off

function hzlx(x) %绘制x的图像

[m n] = size(x); hold on for i = 1:m

plot([x(i,3) x(i,5)],[x(i,4) x(i,6)],'k:') end hold off

function z = bhxz(x,y) %选出x中y区的标号,只是分区域 xzq = x(:,4);

xzr = ismember(xzq,y); z = x(xzr,:); z = z(:,1);