How to compute shortest path in Graph ?
7 views (last 30 days)
Show older comments
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);
0 Comments
Answers (1)
Matt J
on 20 Apr 2023
13 Comments
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
See Also
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!