CODEWITHSUNDEEP
matlabgraphdistancepath-findingadjacency-matrix
sn at
sn at

Reputation: 61

Using Dijkstra algorithm in MATLAB

I found this function: 

 function [dist,path] = CSDG_Dijkstra_SP(nodes,segments,start_id,finish_id,L,PlotFlags);

which allows me to calculate the the shortest distance and path between points on a map. The inputs I need are nodes, segments, start_id, and finish_id. I already have the following:

xyNode=randi([1,100],N,2);
ID=[1:N]'
nodes=[ID,xyNode(:,1),xyNode(:,2)];

and start_id is the number of the nodes among N nodes that I have in my map. finish_id is for another node (different from this N nodes. It is the sink node) which is placed in certain position (center of the map). For this I wrote:

for n=1:N
      start_id=n;
      finish_id=(100*sqrt(N)/2),(100*sqrt(N)/2);
      [dist,path]=CSDG_Dijkstra_SPT(nodes,segments,start_id,finish_id)
      output(:,:,n)=[dist,path];
  end

As it is defined in this function, the input segments should be an Mx3 matrix with the format [ID N1 N2], where ID is an integer, and N1, N2 correspond to entry number in the nodes list.

Two nodes, N1 and node N2, are said to be "able to communicate" (i.e. have an undirected edge/segment between them) only if the distance between them is less than 100*sqrt(5).

How can I get the segments input with this information?

Upvotes: 0

Views: 1435

Answers (1)

Dev-iL
Dev-iL

Reputation: 24169

You should compute the pairwise distance between your points, then filter it according to the threshold, then the remaining distances are used to construct the "valid" segments.

function varargout = q43223243(N, TRSH, MAX_DST)
if nargin == 0
%% DEFINITIONS:
N = 50;
TRSH = 100*sqrt(5);
MAX_DST = 1000;
end
%% The rest...
xyNode = randi(MAX_DST,N,2);
ID = 1:N;
nodes = [ID(:),xyNode(:,1),xyNode(:,2)];
% Find pairwise distance:
D = tril(pdist2(xyNode,xyNode)); % symmetric, so we only take the bottom.
D(D > TRSH | D == 0) = NaN;
% Find positions of valid edges:
[I,J] = ind2sub(size(D), find(~isnan(D)));
% Finally construct the segments array:
segments = [I, J, D(~isnan(D))];
% Outputs
if nargout > 0
  varargout{1} = nodes;
  varargout{2} = segments;
else
  figure();
  line(xyNode(:,1),xyNode(:,2),'LineStyle','none','Marker','o'); hold on;
  gplot(~isnan(D),xyNode,'-r');
end

Example output:

enter image description here

Upvotes: 0

Related Questions