Dijkstra 알고리즘 MATLAB
1524 단어 학창 시절
function [min,path] =dijkstra(w,start,terminal)
n=size(w,1);
label(start)=0;
for i=1:n
if i~=start
label(i)=inf;
end
end
s(1)=start;
u=start;
while length(s)(label(u)+w(u,v))
label(v)=(label(u)+w(u,v));
f(v)=u;
end
end
end
v1=0;
k=inf;
for i=1:n
ins=0;
for j=1:length(s)
if i==s(j)
ins=1;
end
end
if ins==0
v=i;
if k>label(v)
k=label(v);
v1=v;
end
end
end
s(length(s)+1)=v1;
u=v1;
end
min=label(terminal);
path(1)=terminal;
i=1;
while path(i)~=start
path(i+1)=f(path(i));
i=i+1;
end
path(i)=start;
L=length(path);
path=path(L:-1:1);
////
clc
clear;
n = 130;
w = xlsread('TimedataC.xlsx');
M = max(max(w)) * n^2;
w = w + ((w == 0) - eye(130)) * M;
for i = 9:68
for j = 1:2
[min,path] =dijkstra(w,i,j);
D(i-8,j) = min;
len = length(path);
for k = 1:len
P(2 * (i - 9) + j,k)= path(1,k);
end
end
end
fprintf('DONE!');
xlswrite('C-D-Fshortesttime.xlsx',D);// ,
xlswrite('C-D-Ftimepass.xlsx',P);