How to compute shortest path in Graph ?

7 views (last 30 days)
charu shree
charu shree on 20 Apr 2023
Commented: Walter Roberson on 21 Apr 2023
Hello all, I am trying to compute shortest path in a following graph but not getting it correctly.
Suppose there are 15 small mobile towers which can act as source as well as target and 1 Big mobile tower which will only act as target and are modelled as below:
My query is how to compute the shortest path between sources (sr) and targets (ta) in this Graph. Any help in this regard will be highly appreciated.
diff_smt = 15; % different number of small mobile towers
bmt = 1; % only one big mobile tower which is target
idx_bmt = diff_smt +1; % index of big mobile tower (target)
sr = [1 1 1 2 2 2 3 3 4 4 4 5 5 5 6 6 6 7 7 7 8 8 8 9 9 9 10 10 10 11 11 12 12 13 13 13 14 14 15 15 15]; % various possible sources
ta=randi([2,16],1,length(sr)); % various possible targets
G = graph(sr,ta);
plot (G);

Answers (1)

Matt J
Matt J on 20 Apr 2023
You can use the shortestpath command.
  13 Comments
Matt J
Matt J on 21 Apr 2023
Edited: Matt J on 21 Apr 2023
If it is okay and your question has been answered, please do Accept-click the answer.
Walter Roberson
Walter Roberson on 21 Apr 2023
sr = [1 2 2 2 3 3 3 4 5];
ta = [2 3 6 8 4 6 7 6 6];
G = graph(sr, ta);
plot(G)
But by construction each node in sr is connected to each node in ta, so the distance between them is always 1.
If you were asking for the path between each node and every other node then that would be do-able by looping with shortestpathtree
nodes = 1 : 8;
numnodes = length(nodes);
for idx = 1 : numnodes
focus = nodes(idx);
TR = shortestpathtree(G, focus, setdiff(nodes, focus));
figure
p = plot(G);
highlight(p, TR, 'EdgeColor', 'r');
title("node " + focus)
end

Sign in to comment.

Categories

Find more on Graph and Network Algorithms in Help Center and File Exchange

Community Treasure Hunt

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

Start Hunting!