Вершина с минимальным расстоянием до n других вершин

Question

Учитывая ориентированный, взвешенный, циклический граф и минимальное расстояние пути между вершинами, заданными m (x, y), найдите вершину v, которая минимизирует m (a, v) + m (b, v) + m (c , v) + ... для n вершин a, b, c ...

Например, если граф был ненаправленным, и мы хотели, чтобы вершина v с минимальными путями к вершинам a и b, v была бы просто вершиной в центре минимального пути от a до b.

Я могу представить подход, включающий обход глубины и т. Д., Но хотел спросить, что бы SO предложил - Спасибо, надеюсь, это было ясно.

Answer 1

Теперь, когда я думаю об этом немного больше, вам, вероятно, стоит взглянуть на Двунаправленный поиск .

Основной идеей было бы запустить Dijkstra с каждого из ваших узлов запросов (a, b, c, ...) одновременно. Первая найденная всеми вершина - это ваша результирующая вершина.

Вы можете реализовать это, поместив все триплеты (не посещенные вершины, расстояния, вершины запроса), с которыми вы сталкиваетесь, в одну приоритетную очередь (отсортированную по расстоянию) и обработайте ее подобно Dijkstra. Вам нужно будет пометить вершины, которые вы видели, узлом запроса, из которого вы их достигли. Если вершина помечена всеми вершинами запроса, то это ваш результат (назовем его медианной вершиной).