在 MATLAB 中使用 Dijkstra 算法

Question

我找到了这个函数：

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

这让我可以计算地图上各点之间的最短距离和路径。我需要的输入是 nodes、segments、start_id 和 finish_id。我已经有以下内容：

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

和 start_id 是我地图中 N 个节点中的节点数。 finish_id 是另一个节点（不同于这个 N 节点。它是汇节点）放置在某个位置（地图的中心）。为此我写道：

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

正如此函数中定义的那样，输入 segments 应该是格式为 [ID N1 N2] 的 Mx3 矩阵，其中 ID 是整数，N1 , N2 对应于 nodes 列表中的条目号。

两个节点，N1和节点N2，被称为"able to communicate"（即有一个未定向 edge/segment它们之间）仅当它们之间的距离小于 100*sqrt(5) 时。

如何使用此信息获取段输入？

Answer 1

你应该计算你的点之间的成对距离，然后根据阈值过滤它，然后剩余的距离用于构建 "valid" 段。

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

在 MATLAB 中使用 Dijkstra 算法

Using Dijkstra algorithm in MATLAB

matlab

graph

distance

path-finding

adjacency-matrix

示例输出：