iGraph R 中连接多个节点的最短路径

Question

我在 R 中有一个 iGraph 网络，想找到连接网络中多个节点的最短路径（假设节点 1、3、4、7）。有没有可以做到这一点的功能？类似于 all_simple_paths 但对于一个全球解决方案？

解决方案应该类似于以黄色突出显示的路径。请注意，即使 1->2->4 与 1->3->4 一样短，也未选择 1->2->4。

library(igraph)
tree <- graph.tree(n = 8, children = 2, mode = "out")
tree <- add_edges(tree, c(3,4, 3,5))
plot(tree)

Answer 1

经过一番挖掘，我想我找到了自己问题的答案。我所描述的是最小生成树问题的变体，称为 Steiner 树问题。

Given a weighted graph G = (V, E), a subset S ⊆ V of the vertices, and a root r ∈ V , we want to find a minimum weight tree which connects all the vertices in S to r. [ref]

原来有一个名为 SteinerNet 的 R 包是专门为这些类型的问题创建的。我无法直接安装他们的包，但能够从他们的 GitHub repo.

复制相关的源代码

out <- steinertree(type = "KB", terminals = c(1,3,4,7), graph = tree)

这个包完全符合我的要求，它甚至生成了一个漂亮的图表！

>out[[2]]
IGRAPH fbb52e5 UN-- 4 3 -- Tree
+ attr: name (g/c), children (g/n), mode (g/c), name (v/c), color (v/c)
+ edges from fbb52e5 (vertex names):
[3] 1--3 3--4 3--7
>plot(out[[1]])

iGraph R 中连接多个节点的最短路径

Shortest path connecting multiple nodes in iGraph R

r

shortest-path

igraph