Набор кратчайших путей с несколькими начальными и множественными концами

У меня проблема с кратчайшим путем в ориентированном взвешенном графе. Я знаю Dijkstra, BFS, DFS. Однако у меня есть a set of vertices S для отправных точек и a set of vertices E to end. S и E не пересекаются. Итак, как я могу найти набор ребер с минимальной суммой веса ребер? Набор ребер не обязательно должен включать все вершины в S, но должен reach all vertices in E. Должен ли я начать с Дейкстры для всех перестановок {Si, Ei} и оптимизировать, или я пропущу какой-либо важный алгоритм, который я должен знать? Или даже я слишком много думаю....


optimization algorithm computer-science shortest-path dijkstra
person ZhijieWang    schedule 01.05.2014    source источник
comment
Добавьте две вершины, начальную, соединенную со всеми вершинами в S, и конечную, соединенную со всеми вершинами в E. Запустите Dijkstra на новом графике.   -  person user58697    schedule 01.05.2014
comment
однако кратчайший путь (множество) достигнет End, но не обязательно достигнет всех вершин в E.   -  person ZhijieWang    schedule 01.05.2014
comment
Если путь от начала до конца является кратчайшим, он является кратчайшим среди всех путей от {S} до {E}. Если я полностью неправильно понял вопрос.   -  person user58697    schedule 01.05.2014
comment
Предположим, что в наборе E есть E1 и E2. Вы можете достичь End через E1 и полностью пропустить E2.   -  person ZhijieWang    schedule 01.05.2014

Ответы (1)


arrow_upward
3
arrow_downward

Если я вас правильно понял, вы хотите найти дерево минимального веса в графе, содержащем все вершины E и хотя бы одну вершину из S.

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

Существует простое решение DP, которое работает за O (2 ^ n * (n + m)): пусть f (S) будет стоимостью минимального дерева в графе, которое охватывает все узлы в S. Можно показать, что существует такое дерево T, что вес T \ {x} равен f(S \ {x}) для некоторого x, поэтому переход можно выполнить за O(n + m).

person Niklas B.    schedule 01.05.2014
comment
@user1505108 user1505108 Ну, тогда это не совсем очевидно, но проблема сложная. - person Niklas B.; 01.05.2014
comment
@ user1505108 Я добавил алгоритм DP O (2 ^ n * (n + m)) , если это полезно. По крайней мере, это не зависит экспоненциально от количества ребер. - person Niklas B.; 01.05.2014