Как мы можем эффективно реализовать дугу максимального набора фиксированной мощности? - PullRequest
0 голосов
/ 20 декабря 2018

Я работаю над решением следующей проблемы и реализую решение в C ++.

Предположим, что у нас есть ориентированный взвешенный граф G = (V, A, w) и P множество людей.

Мы получаем такое количество запросов, что каждый запрос дает человеку p и две вершины s и d и просит вычислить минимальный взвешенный путь между s и d для человека p.Один человек может иметь несколько путей.

После окончания всех запросов у меня есть число k <= | A |и я должен дать k дуг так, чтобы число людей, использующих хотя бы одну из k дуг, было максимальным (это проблема максимального покрытия).</p>

Для решения первой части я реализовал алгоритм Джикистры с использованием priority_queue и вычисляю минимальный вес между s и d.(Это хороший способ сделать?)

Чтобы решить вторую часть, я сохраняю для каждой дуги набор людей, которые используют эту дугу, и я использую жадный алгоритм для вычисления набора дуг (на каждом этапеЯ выбираю дугу, используемую наибольшим числом непокрытых лиц).(Это хороший способ сделать это?)

Наконец, если мои алгоритмы - это товар, как я могу эффективно реализовать их в C ++?

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...