matlab coding - finding shortest path problem

Lately I've been trying to learn MATLAB and there's this project that have been assigned to me which I'm trying to do. the description of the project is as follows:

we have a set of 100 points:

1-choose 10 random points and color them red , those are points we can not go to.(others shall be green).

2-take point (0,0) as the start and color it blue

3-randomly choose the end point and color it black

then the assignment asks us to find the shortest path from the start point to the end one (and to graph it).

so I plotted the dots in the following code:

clc;clear;close all

all_dots=zeros(10,10);

red_dots_x=zeros(1,10);

red_dots_y=zeros(1,10);

for counter=1:10

all_dots(randperm(10,10),randperm(10,10))=1;

red_dots_x=randi(10,1,10);

red_dots_y=randi(10,1,10);

end

for counter2=1:10

all_dots(red_dots_x(counter2),red_dots_y(counter2))=2;

end

all_dots(1,1)=3;

x1=randi([2,10]);

y1=randi([2,10]);

all_dots(randi(10),randi(10))=4;

for i=1:10

for j=1:10

if all_dots(i,j)==1

figure(1);plot(i,j,'og','MarkerFaceColor','g');hold on;

else if all_dots(i,j)==2

figure(1);plot(i,j,'or','MarkerFaceColor','r');hold on;

else if all_dots(i,j)==3

figure(1);plot(i,j,'ob','MarkerFaceColor','b');hold on;

else if all_dots(i,j)==4

figure(1);plot(i,j,'ok','MarkerFaceColor','k');hold on;

end

end

end

end

end

xlim([0,11]);ylim([0,11]);

end

now I have to get on finding the shortest path. after a lot of search I found two algorithms that can be useful for my intention:

1-BFS

2-Dijkstra (setting all the weights as 1)

3- also there are some other ways suggested on other communities like mathexchange you can read them on comments.

and again after reading on the MATHWORKS website I found out there are built-in functions for those algorithms. but the problem is I PREFER not to use those built-ins because the course coach haven't taught them (so I may not get the full point) and also I neither have an source-destination set nor the adjacency matrix required for using those functions.

literally ANY kind of help even for the code I have already written is very much appreciated.

p.s: I am allowed to move diagonaly, vertically and horizontally and all distances (even the diagonal distance) between points are the same.

Answer 1

[David Hill]

e=[];
%generate adjacency matrix
K=1:100;
a=11:10:81;b=20:10:90;c=2:9;d=92:99;
e=[e;[a',a'+1];[a',a'+10];[a',a'-10];[a',a'-9];[a',a'+11]];
e=[e;[b',b'-1];[b',b'+10];[b',b'-10];[b',b'-11];[b',b'+9]];
e=[e;[c',c'+10];[c',c'-1];[c',c'+1];[c',c'+9];[c',c'+11]];
e=[e;[d',d'-10];[d',d'-1];[d',d'+1];[d',d'-9];[d',d'-11]];
e=[e;[1,2];[1,11];[1,12];[10,9];[10,19];[10,20];[100,90];[100,89];[100,99];[91,81];[91,82];[91,92]];
K([a,b,c,d,[1 10 91 100]])=[];
for k=K
    r=[k-1,k+1,k+10,k-10,k-11,k-9,k+11,k+9];
    r=r(r>0&r<101);
    e=[e;[repmat(k,length(r),1),r']];
end
%create graph
g=graph(e(:,1),e(:,2));
a=full(adjacency(g));
[x,y]=meshgrid(1:10);
%determine red and black dots
r=randperm(99,11)+1;
[rows,cols]=ind2sub([10,10],r);
%plot
scatter(1,1,'b','filled');
hold on;
scatter(rows(1:10),cols(1:10),'r','filled');
scatter(rows(11),cols(11),'k','filled');
scatter(x,y,'k');
%delete red dots from graph
a(:,r(1:10))=0;a(r(1:10),:)=0;
g=graph(a);
%determine shortest path
P=shortestpath(g,1,r(11));
[rows,cols]=ind2sub([10,10],P);
%plot shortest path
plot(rows,cols);
hold off;

[farbod bijary]

thanks a lot. your code had truely helped me. just one question. is there any alternative to use instead of "graph" function since I'm using Matlab 2015a and that function had been introduced in 2015b.

Answer 2

[farbod bijary]

o after a lot of search a CS student helped me solve the problem. this is the algorithm:

1-from any point (initially the start point) find all the adjacent points and list them.

2-from the list delete the unavailable points (red ones).

3-for all available points find the euclidean distance from the end point.

4-choose the available adjacent point in which you will have the least distance from the end point.

5-while you haven't reached the end point repeat the loop.

it was really fascinating for me that non of the BFS,DFS or Dijkstra algorithms were needed for this problem. for further use I will put the code for this project.

clc;clear;close all

all_dots=zeros(10,10);

red_dots_x=zeros(1,10);

red_dots_y=zeros(1,10);

for counter=1:10

all_dots(randperm(10,10),randperm(10,10))=1;

red_dots_x=randi(10,1,10);

red_dots_y=randi(10,1,10);

end

for counter2=1:10

all_dots(red_dots_x(counter2),red_dots_y(counter2))=2;

end

all_dots(1,1)=3;

x1=randi([2,10]);

y1=randi([2,10]);

rand1=randi(10);

rand2=randi(10);

all_dots(rand1,rand2)=4;

for i=1:10

for j=1:10

if all_dots(i,j)==1

figure(1);plot(i,j,'og','MarkerFaceColor','g','MarkerSize',15,'MarkerEdgeColor','b');hold on;

else if all_dots(i,j)==2

figure(1);plot(i,j,'or','MarkerFaceColor','r','MarkerSize',15,'MarkerEdgeColor',[107 76 154]./255);hold on;

else if all_dots(i,j)==3

figure(1);plot(i,j,'ob','MarkerFaceColor','b','MarkerSize',15);hold on;

else if all_dots(i,j)==4

figure(1);plot(i,j,'ok','MarkerFaceColor','k','MarkerSize',15);hold on;

end

end

end

end

end

xlim([0,11]);ylim([0,11]);

end

dot=[1,1];

counter100=1;

while dot(1)~=rand1 || dot(2)~=rand2

steper(counter100,:)=dot;

dots=[dot(1)+1,dot(2);dot(1),dot(2)+1;dot(1)-1,dot(2);dot(1),dot(2)-1;dot(1)+1,dot(2)+1;dot(1)+1,dot(2)-1;dot(1)-1,dot(2)+1];

for i=1:7

if dots(i,1)>=1 && dots(i,2)>=1 && all_dots(dots(i,1),dots(i,2))~=2

availdots(i,:)=dots(i,:);

end

end

sizea=size(availdots);

for i=1:sizea(1,1)

distances(i)=hypot(availdots(i,1)-rand1,availdots(i,2)-rand2);

end

[m,next]=min(distances);

dot=availdots(next,:);

counter100=counter100+1;

end

sth=size(steper);

steper(sth(1,1)+1,:)=[rand1,rand2];

plot(steper(:,1),steper(:,2),'k','LineWidth',8);

of course the approach to use BFS DFS or Dijkstra are much more reliable and they can be developed to bigger examples but for now this seems to be working.

p.s: I will still appreciate any help about how this method is exactly working.