Кратчайший путь, соединяющий несколько узлов в iGraph R

Question

У меня есть сеть iGraph в R, и я хотел бы найти кратчайший путь, соединяющий несколько узлов в моей сети (скажем, узлы 1,3,4,7). Есть ли функция, которая может сделать это? Что-то вроде all_simple_paths, но для одного глобального решения?

Решение должно выглядеть примерно как путь, выделенный желтым цветом. Обратите внимание, что 1-> 2-> 4 не выбран, хотя он такой же короткий, как 1-> 3-> 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

После некоторых копаний, я думаю, что нашел ответ на свой вопрос. То, что я описывал, - это вариация задачи минимального связующего дерева, называемая проблемой дерева Штейнера .

. Для заданного взвешенного графа G = (V, E), подмножество S ⊆ V вершин и a root r ∈ V, мы хотим найти дерево минимального веса, которое соединяет все вершины из S с r. [ref]

Оказывается, существует пакет R с именем SteinerNet, созданный специально для этих типов проблем. У меня были проблемы с установкой их пакета напрямую, но я смог скопировать соответствующий исходный код из их 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]])