How to compute shortest path in Graph ?

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

Answer 1

[Matt J]

You can use the shortestpath command.

[charu shree]

I tried using the shortestpath command in the following way but every time I am getting d as 1.

[TR,d] = shortestpathtree(G,sr(1),ta(1));

I am not getting why d value (i.e., shortest path ) is always 1 while 'ta' elements are random.

[Torsten]

Think about what it means if you create the graph as

G = graph(sr,ta)

Then it should become obvious that the distance between sr(1) to ta(1) is always 1 (as will be the case for every pair sr(i) to ta(i)).

[charu shree]

Ok sir. Is there any way in MATLAB that will give shortest path between every element of sr and ta ?

I think if sr is 1×41 vector and ta is also 1×41 vector then shortest path vector should also be 1×41.

[Walter Roberson]

Each source has a separate path, so if you say that "shortest path vector should also be 1 x 41" then the only way to handle that is if it is cell array "vector".

You have multiple sources and multiple targets. Are you wanting to get, for each source, the shortest path to the nearest target? (If so then what should be done if there are multiple equally-close targets) ?

Or for each entry in sr are you asking for the shortest path to the corresponding element in ta ?

The graph you are creating implicitly declares that each element of sa is directly connected to the corresponding element in ta. I suspect that is not what you want -- that instead you have some other connection pattern -- for example you might have coordinates for each small tower and each small tower might be considered connected to every small tower that is within a certain distance of it.

[charu shree]

Yes sir I want, for each entry in 'sr' the shortest path to the corresponding element in 'ta'.

[Walter Roberson]

Well, since you are creating a graph() object in which each sr entry is indicated as directly connected to each corresponding ta entry, then the output you would expect in such a case would be

[sr(:), ta(:)]

that is, you start at the sr node and you take a single step to the ta node. Well, except, I suppose, where sr(K) and ta(K) happen to be exactly the same node, which is a possible situation for the way you generate ta values -- in such a case, really the output should just be the sr entry by itself without the (identical) ta entry.

The situation would be different if you had a different graph, such as I was discussing before, where nodes are connected to "nearby" nodes.

Though there is one other possibility: if you were to graph(sr, ta) and also pass in cost / distance information, then there would be the possibility that the direct connection might not be the shortest path.

A note in that regard: if the "cost" corresponds to Euclidean Distance, and if each node is directly connected to its target (which it is the way you construct it), then it can be shown mathematically that the shortest path is always the direct step.

In the case of cell transmissions, in real life, the "cost" of transmission between two nodes can be greater than implied by the Euclidean Distance, because there can be obstacles in the way that cause reflections or reduce the transmission power. Going around a high-rise office might be better than going through it.

[charu shree]

Ok Thank u sir for your answer....

Basically I am new to the Graph theory so may not have complete understanding....

Specifically I want to generate the following Graph in MATLAB as shown in the image.

[Matt J]

How is this smaller graph related to your original question? Your original graph had 15 nodes.

[charu shree]

Yes sir....it's not similar to my original question...but For example purpose I had taken this smaller graph

[Matt J]

The use of the new example doesn't seem to add any new information to the question that would change the answer. The reason you are getting a shortest distance of 1 to all target nodes in the original graph is because that is indeed the shortest distance, as others have explained.

Your new graph does not show which nodes form source-target pairs, but if those pairs are always neighboring nodes, as in your first graph, then the shortest distance will again be 1.

[charu shree]

Ok sir...

[Matt J]

If it is okay and your question has been answered, please do Accept-click the answer.

[Walter Roberson]

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