Алгоритм кратчайшего пути: множественный источник, ближайший пункт назначения

Question

Алгоритмы, такие как алгоритм Беллмана-Форда и алгоритм Дейкстры, заключаются в поиске кратчайшего пути из одной начальной вершины на графике для каждой другой вершины. Их множественная исходная версия может быть достигнута путем изменения всех краев и обработки адресата в качестве начального узла.

Я хотел бы расширить, что найти «барицентр» из источников на графике, т.е. вершины, которая является «ближе» к множеству источников, находя «справедливый» путь к «взаимному согласию» вершина.

Есть ли алгоритмы, которые уже предоставляют это? Кто они такие?

Answer 1

Floyd–Warshall algorithm

Я думаю, что вы хотите, чтобы вычислить "Graph Эксцентриситет" из источников (S1, S2, ... Sn-1, Sn).

1. Использовать алгоритм Floyd-Warshall для расчета всей пары самых коротких путей в графе.
2. Найти узел результата V в графе, который является минимальной суммой (d [v, S1] + d [v, S2] + d [v, S3] .... d [v, Sn-1] + d [v, Sn])

Дополнительная информация:

Graph Eccentricity

ОБНОВЛЕНИЕ

Может быть, находя существовавший узел V в графике G (V, E), которое расстояние до S все равны, не реалист IC. Вы можете рассчитать отклонение от стойки (d [v, S1], d [v, S2], d [v, S3] .... d [v, Sn-1], d [v, Sn]) между a диапазон, который больше или равен 0 и меньше определенного значения, которое вы выберете.