Dijkstra的matlab实现

任务描述：生成20x20个点，使用Dijkstra算法让找出点(1, 1)到(20, 20)的最短路径，期中有随机的120个点是不通的，这120个点不包括起点和终点

随机五次的实验结果图，代码在后面

1. Figure 1

2. Figure 2

3. Figure 3

4. Figure 4

5. Figure 5

Code

• there are 4 parts, the major parts are part2: Initialization and part3: Loop like the ppt shown during class
• the algorithm complexity is O(n^2)
• the least-cost-path tree can be seen in cell F
• the cost from start point to any other can be seen in cell D
• The set N contains the points added at each step
• you can edit the start_x、start_y、target_x、target_y to set the start position and target position when the points you tend to set are not removed and when it sure will have a feasible path

%%
%Part1 define the variables
clc;clear;

start_x = 1; % start point
start_y = 1;

target_x = 20; % target pont
target_y = 20;

w = 20; %columns
h = 20; %Rows

remove_amount = 120;
remain_amount = h * w - remove_amount;
total_pont = h * w;

D = zeros(h, w); %Used to record the distance from the point to the starting point
P = ones(1,total_pont); %Whether the location was removed
remove = randperm(total_pont - 2, remove_amount);

F = cell(h, w); % form the least-cost-path tree 

for i = 1:size(remove,2)
    P(remove(i)+1) = 0; % +1 Make sure the starting point is not removed
end



N = cell(1, remain_amount);
N{1} = [start_x start_y]; %Add point u to N set

ix = 1; %scanning point
jy = 1;

x = 1; %the position of a
y = 1;

x_p = target_x; %path
y_p = target_y;

%%
%Part2 Initialization

for i = 1:h
    for j = 1:w
        if P((i-1)*w + j) == 1 %if a point has been removed
            Cub  = sqrt((i-start_x)^2+(j-start_y)^2); %Calculate Cb
            if(Cub < 2 && Cub > 0) %to judge if it is around u
                D(i,j) = Cub;
                F{i,j} = [start_x,start_y];
            else
                D(i,j) = 999;
                F{i,j} = [999,999];
            end
        else
            F{i,j} = [999,999];
            D(i,j) = 999;
        end
    end
end

%%
%Part3 Loop here

for p = 1:remain_amount %steps needed

    Da = D;
    for i = 1:p
        Da(N{i}(1),N{i}(2)) = 999; %Exclude points in set N when looking for a
    end
    [x,y] = find(Da==min(min(Da)));
    N{p+1} = [x(1) y(1)];

    for q = 1:total_pont
        if(jy > w)
            jy = 1;
            ix = ix + 1;
        end
        if P((ix-1)*h + jy) == 1
            Cab = sqrt((ix-x(1))^2+(jy-y(1))^2); %Calculate Cab     
            a = cellfun(@(x)isequal(x,[ix jy]),N); %to judge whether a point is in N set
            if(Cab < 2 && ~ismember(1, a) && Cab > 0)
                D(ix,jy) = min(D(ix,jy),D(x(1),y(1)) + Cab);
                if(D(ix,jy) < (D(x(1),y(1)) + Cab))
                    F{ix,jy} = F{ix,jy}; %record the point for the least-cost-path tree 
                else
                    F{ix,jy} = [x(1) y(1)];
                end
            end
        end
        jy = jy + 1;
    end
    ix = 1;
    jy = 1;
    p %Observe the number of steps
end

%%
%Part4 plot here

for i = 1:h
    for j = 1:w
        if(P((i-1)*w+j) == 1)
            plot(i,j,'go','MarkerFaceColor','g');
            hold on;
        else
            plot(i,j,'ro','MarkerFaceColor','r');
            hold on;
        end
    end
end

% Query the forwarding tree and record the coordinates of each pair of coordinate points for drawing
while(~(target_x == start_x && target_y == start_y))
    x_p = [x_p F{target_x,target_y}(1)];
    y_p = [y_p F{target_x,target_y}(2)];
    temp = target_x;
    target_x = F{target_x,target_y}(1);
    target_y = F{temp,target_y}(2);
end

axis([0, h + 1, 0, w + 1]);
plot(x_p,y_p,'b-');