# How to compute shortest path in Graph ?

1 visualizzazione (ultimi 30 giorni)
charu shree il 20 Apr 2023
Commentato: Walter Roberson il 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);
##### 0 CommentiMostra -2 commenti meno recentiNascondi -2 commenti meno recenti

Accedi per commentare.

### Risposte (1)

Matt J il 20 Apr 2023
You can use the shortestpath command.
##### 13 CommentiMostra 11 commenti meno recentiNascondi 11 commenti meno recenti
Matt J il 21 Apr 2023
Modificato: Matt J il 21 Apr 2023
Walter Roberson il 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

Accedi per commentare.

### Categorie

Scopri di più su Graph and Network Algorithms in Help Center e File Exchange

### Community Treasure Hunt

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

Start Hunting!

Translated by