matlab编程动态规划最短路径问题

发布网友发布时间：2022-04-24 01:58

共2个回答

热心网友时间：2023-10-20 10:56

以前搞建模在网上下到的代码，不是自己编的，但经过试验可以用，分享了：

function len=dijkstra(Input)
%最短路Dijkstra算法,同时给出路径，input为图矩阵

row=size(Input,1);

%赋初值
% s_path=1;
distance=inf*ones(1,row);
distance(1)=0;
% flag(1)=1;
temp=1;

%求起点到各点的最短路的权
% s_path=ones(1,3);
while length(s_path)<row
pos=find(Input(temp, : )~=inf);
n=length(pos);
flag=ones(1,n);
for i=1:n
if (isempty(find(s_path==pos(i),1)))&&(distance(pos(i))>...
(distance(temp)+Input(temp,pos(i))))
distance(pos(i))=distance(temp)+Input(temp,pos(i));
flag(pos(i))=temp;
end
end
k=inf;
for i=1:row
if (isempty(find(s_path==i,1)))&&(k>distance(i))
k=distance(i);
temp_2=i;
end
end
s_path=[s_path,temp_2];
temp=temp_2;
end

%用追溯法得到起点到各点的最短路的路线
len=zeros(1,row);
for endpoint=1:row
path=0; %初始化
path(1)=endpoint;
i=1;
while path(i)~=1
path(i+1)=flag(path(i));
i=i+1;
end
path(i)=1;
path=path(end:-1:1); %最短路径
short_distance=distance(endpoint); %最短路径权
len(endpoint)=short_distance; %起点到各点的最短距离
pathall=path; %总路径矩阵
end

len=len(25:end);

%{
disp('起点到各点的最短路径：');
celldisp(pathall);
%设法只画出最短路径
em=find(w==inf);
w(em)=0;
h = view(biograph(w,[],'ShowWeights','on'));
%}
邮箱给你发了个资料，多年前搞的，估计是忘了，也许这个函数有点问题，你按资料里的做吧

热心网友时间：2023-10-20 10:57

有没有能够动态画出最短路径的程序啊，求赐教

热心网友时间：2023-10-20 10:56

热心网友时间：2023-10-20 10:57

有没有能够动态画出最短路径的程序啊，求赐教