Shortest path constrained to use specific nodes

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

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

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.

Categories

Find more on Graph and Network Algorithms in Help Center and File Exchange

Products


Release

R2020b

Community Treasure Hunt

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

Start Hunting!