Dijkstra's Algorithm

13 Ansichten (letzte 30 Tage)
Christian Basa
Christian Basa am 16 Apr. 2021
Kommentiert: Christian Basa am 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

Antworten (1)

Stephan
Stephan am 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 Kommentar
Christian Basa
Christian Basa am 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.

Melden Sie sich an, um zu kommentieren.

Tags

Community Treasure Hunt

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

Start Hunting!

Translated by