How to find shortest distance in 3D?

29 次查看(过去 30 天)
Hello, Everyone!
I am trying to find the shortest path by using dijkstra's algorithm and I need to input 3-Dimensional nodes into the program.
Each 3-Dimensional nodes have x, y, z coordinates. I am trying to use Nx3 matrix to represent it or maybe Nx4 matrix include the node ID.
I found that there is a function which called graphshortestpath in matlab function.
I want to know that is it possible to input 3-Dimensional nodes and plot a graph to demonstrate the result?
If yes, please tell me how to do it or give me some examples. If the function cannot do it, please tell me how to do it by other methods.
Thank you very much!

采纳的回答

Akira Agata
Akira Agata 2019-2-19
You can use shortestpath function to find the shortest path between selected nodes. I believe the solution would be looks like the following.
% Generate 3D nodes coordinages (x,y,z) for 10 nodes
rng('default') % for reproducability
Position = 10*rand(10,3);
% Calculate euclid distance between each nodes
d = pdist(Position);
% Set distance to 0 for 30 node-pairs
pt = randperm(numel(d),30);
d(pt) = 0;
% Convert to Adjacency matrix
d = squareform(d);
% Generate Graph object and store XYZ coordinates in it
G = graph(d);
G.Nodes = array2table(Position,'VariableNames',{'X','Y','Z'});
% Calculate shortest path between node 1 and 10
[P,L] = shortestpath(G,1,10);
% Visualize the result
figure
h = plot(G,'XData',G.Nodes.X,'YData',G.Nodes.Y,'ZData',G.Nodes.Z);
highlight(h,P,'EdgeColor','r','LineWidth',2)
% Display the path length
disp(L)
graph.png
  7 个评论
Akira Agata
Akira Agata 2019-2-26
Hi Antonio-san,
I believe you should use sparse matrix as an Adjacency matrix when number of nodes is huge. For example, the following code can generate, visualize and calculate shortest path (between node 1~10) of a graph with 10000 nodes.
% Generate sparse symmetric non-negative random matrix
A = sprandsym(10000,0.001);
idx = A < 0;
A(idx) = abs(A(idx));
% Generate graph
G = graph(A)
% Visualize the graph G
figure
plot(G)
% Calculate shortest path between node 1 and 10
[P,L] = shortestpath(G,1,10);
Akira Agata
Akira Agata 2019-2-26
Regarding a second question, the function shortestpath uses an well-known Dijkstra algorithm. If you type "edit shortestpath" in a command window, you can look at code of the function.

请先登录,再进行评论。

更多回答(0 个)

类别

Help CenterFile Exchange 中查找有关 Dijkstra algorithm 的更多信息

标签

尚未输入任何标签。

Community Treasure Hunt

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

Start Hunting!

Translated by