How to find shortest distance in 3D?

Antonio Smith (view profile)

on 16 Feb 2019
Latest activity Commented on by Akira Agata

on 26 Feb 2019

Akira Agata (view profile)

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!

Tags

No tags entered yet.

Akira Agata (view profile)

on 19 Feb 2019

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;
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)

Antonio Smith

Antonio Smith (view profile)

on 24 Feb 2019
HI Akira-san,
Thank you very much for your help.
I have uploaded around 3000 nodes and it is success. However, I cannot generate a graph when I upload 10000 nodes. Is it cannot exceed 10000 nodes?
Moreover, I would like to know that what is the difference between function shortestpath and graphshortestpath?
Also, If I want to read the source code of the function shortestpath, is there any method? I tried to type "type shortestpath" in the Command Window, and there is some code but I am not sure that is it the source code of the function shortestpath.
Thanks again!
Akira Agata

Akira Agata (view profile)

on 26 Feb 2019
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 (view profile)

on 26 Feb 2019
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.