How to compute shortest path in Graph ?

2 次查看（过去 30 天）

charu shree 2023-4-20

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/1950513-how-to-compute-shortest-path-in-graph

评论： Walter Roberson 2023-4-21

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

回答（1 个）

Matt J 2023-4-20

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/1950513-how-to-compute-shortest-path-in-graph#answer_1219773

You can use the shortestpath command.

13 个评论
显示 11更早的评论隐藏 11更早的评论

Walter Roberson 2023-4-21

在 MATLAB Online 中打开

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.