MATLAB Answers

Shortest path constrained to use specific nodes

19 views (last 30 days)
Tejas
Tejas on 3 Apr 2021
Edited: Matt J on 3 Apr 2021
Let's say I have a simple graph:
G = graph([1,2,3,4,5],[2,3,4,5,1]);
I want to find the shortest path from 1 to 3. The shortestpath function would give me 1-2-3. But in my case, I have a list of nodes that I can travel on:
nodes = [1,3,4,5];
How can I find the shortest path between any two nodes in the graph that only takes the nodes in that list (which will be 1-5-4-3 in this case)?

Answers (3)

Sulaymon Eshkabilov
Sulaymon Eshkabilov on 3 Apr 2021
Here is an easy solution:
shortestpath(G, 1,3) % Shortest path between 1 and 3
Good luck.
  1 Comment
Tejas
Tejas on 3 Apr 2021
That does not answer my question, since it'll give 1-2-3, and I cannot use 2.

Sign in to comment.


Tejas
Tejas on 3 Apr 2021
Okay, I realised if I assign weights like:
G = graph([1,2,3,4,5],[2,3,4,5,1],[Inf,1,1,1,1]);
Then I do get
shortestpath(G,1,3)
ans =
1 5 4 3
I don't have any other purpose for weights so I can use them in this way.

Matt J
Matt J on 3 Apr 2021
Edited: Matt J on 3 Apr 2021
Why not just analyze a subgraph with the inadmissible nodes removed:
cut=setdiff(1:numnodes(G),nodes);
Gsub=rmnodes(G,cut);

Products


Release

R2020b

Community Treasure Hunt

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

Start Hunting!

Translated by