Учитывая ориентированный граф с взвешенными ребрами, какой алгоритм можно использовать для получения субграфа с минимальным весом, но позволяет перемещаться из любой вершины в любую другую вершину на графе (в предположении, что пути между любыми двумя вершинами всегда существуют).
Существует ли такой алгоритм?
Это выглядит NP-Hard: минимальный вес сильно связан с проблемой подграфа.
Я считаю, что проблема Гамильтонова цикла может быть сведена к ней: для графа G (V, E) построим диграф DG с весом 1 для краев, которые появляются и вес 100 (| V | +1) для ребер, т. DG имеет минимальный вес, сильно связанный с подграфом веса точно | V | тогда и только тогда, когда G имеет гамильтонов цикл.
В этом документе есть алгоритм аппроксимации: http://portal.acm.org/citation.cfm?id=844363
Несмотря на то, что они не были правы сами, не торопясь следить за ссылками Виталия Википедии быстро раскрыли этот алгоритм:
http://en.wikipedia.org/wiki/Chu%E2%80%93Liu/Edmonds_algorithm
Разделить каждый node на граф на два узла. Один node будет принимать все входящие ребра к исходному node, а другой будет иметь все исходящие ребра. Затем отбросьте направление по всем краям, чтобы график не был направлен. Затем вы можете запустить стандартный алгоритм MST на графике (Prim's, Kruskal's), и вы убедитесь, что каждый оригинальный node может перемещаться любым другим оригиналом node.
Это проблема Directed Steiner Tree. Как дерево Штайнера, это NP-Hard.
Здесь вы можете найти некоторые приблизительные алгоритмы:
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.38.8774&rep=rep1&type=ps
Выберите любой node и верните его.
Возможно, вы имели в виду, что подграфик наибольший сильно связанный (возможно меньшее число удаленных узлов) или подграф минимального веса (no node разрешено удаление)?