Asked by Antonio Smith
on 16 Feb 2019

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!

Answer by Akira Agata
on 19 Feb 2019

Accepted Answer

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)

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

Sign in to comment.

Opportunities for recent engineering grads.

Apply Today
## 0 Comments

Sign in to comment.