MATLAB Answers

Dijkstra's Algorithm

5 views (last 30 days)
Christian Basa
Christian Basa on 16 Apr 2021
Commented: Christian Basa on 17 Apr 2021
I was wondering if there's a way to apply Dijkstra's to randomly generated nodes on a plot. I then stored their x and y values into a matrix. I'm trying to find the shortest distance from a source to a destination.
Here's the full code that I have for generating the nodes
%Generating node locations to help aid in the routing of a UAV
%Genuine Nodes represent refill stations
%Malicious Nodes represent areas to avoid
clc;
clear all;
close all;
no_nodes = input('Enter the number of nodes: ');
no_nodes_m = input('Enter the number of malicious nodes: ');
network_length = input('Enter the length of the network: ');
network_width = input('Enter the width of the network: ');
for i = 1:no_nodes
x_loc(i) = network_length*rand;
y_loc(i) = network_width*rand;
%nodes_id(i) = i;
plot(x_loc(i),y_loc(i),'b^','linestyle','none')
text(x_loc(i),y_loc(i),['N',num2str(i)]);
hold on
xlabel('Network Length');
ylabel('Network Height');
grid on
pause(.1);
end
for j = 1:no_nodes_m
x_loc_m(j) = network_length*rand;
y_loc_m(j) = network_width*rand;
%nodes_id_m(j) = j;
plot(x_loc_m(j),y_loc_m(j),'ro','linestyle','none')
hold on;
xlabel('Network Length');
ylabel('Network Height');
grid on
pause(.1);
end
source = rem(round((no_nodes+no_nodes_m)*rand),no_nodes);
if source == 0
source = 15;
end
destination = rem(round((no_nodes+no_nodes_m)*rand),no_nodes);
if destination == 0
destination = 16;
end
figure(1)
plot(x_loc(source),y_loc(source),'b^','linewidth',2);
text(x_loc(source),y_loc(source), 'SRC')
hold on
plot(x_loc(destination),y_loc(destination),'g^','linewidth',2);
text(x_loc(destination),y_loc(destination), 'Destination')
% Location of nodes
% Genuine
genuine = [x_loc; y_loc];
% Malicious
malicious = [x_loc_m; y_loc_m];
% Connecting source and destination
source_loc = [x_loc(source), y_loc(source)];
destination_loc = [x_loc(destination), y_loc(destination)];
p1 = [source_loc(1) destination_loc(1)];
p2 = [source_loc(2) destination_loc(2)];
x = [p1(1) p2(1)];
y = [p1(2) p2(2)];
plot([x(1) y(1)],[x(2) y(2)])
idx = [genuine(1,:); genuine(2,:)];
idx1 = [malicious(1,:); malicious(2,:)];
% distance from origin to destination
d_location = sqrt((destination_loc(1)-0)^2+(destination_loc(2)-0)^2);
d_source = sqrt((source_loc(1)-destination_loc(1))^2+(source_loc(2)-destination_loc(2))^2);
Here's the code i have for Dijkstra's taken from a YouTube video.
function distances = dijkstra(idx, d_location)
N = length(idx);
distances(1:N) = Inf;
visited(1:N) = 0;
distances(d_location) = 0;
while sum(visited) < N
candidates(1:N) = Inf;
for index = 1:N
if visited(index) == 0
candidates(index) = distances(index);
end
end
[currentDistance, currentPoint] = min(candidates);
for index = 1:N
newDistance = currentDistance + idx(currentPoint,index);
if newDistance < distances(index)
distances(index) = newDistance;
end
visited(currentPoint) = 1;
end
end

Answers (1)

Stephan
Stephan on 17 Apr 2021
You could make life easier using Matlab inbuilt graphs functions. One example is shortestpath. All you have to do is read about graphs in Matlabs great documentation, build a graph object following the input restrictions and use the inbuilt capabilities.
  1 Comment
Christian Basa
Christian Basa on 17 Apr 2021
Thanks, that helps a lot. I'm going to look into that. Didn't know matlab already had the function, just got dijkstra's work yesterday so hopefully this is easier.

Sign in to comment.

Tags

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!