Shortest path constrained to use specific nodes

4 次查看（过去 30 天）
Tejas
Tejas 2021-4-3
编辑： Matt J 2021-4-3
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)?

请先登录，再回答此问题。

回答（3 个）

Matt J
Matt J 2021-4-3
编辑：Matt J 2021-4-3
Why not just analyze a subgraph with the inadmissible nodes removed:
cut=setdiff(1:numnodes(G),nodes);
Gsub=rmnodes(G,cut);
Sulaymon Eshkabilov
Here is an easy solution:
shortestpath(G, 1,3) % Shortest path between 1 and 3
Good luck.
Tejas
Tejas 2021-4-3
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.

类别

在 Help Center 和 File Exchange 中查找有关 Graph and Network Algorithms 的更多信息

标签

产品


版本

R2020b

Community Treasure Hunt

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

Start Hunting!

Translated by