Кратчайшее расстояние от всех вершин графа до выделенных

Материал из Algocode wiki
Версия от 22:42, 18 ноября 2019; Глеб (обсуждение | вклад) (Новая страница: «Идею с несколькими стартами в BFS можно применить для такой задачи: Вам дан граф с выделен...»)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Идею с несколькими стартами в BFS можно применить для такой задачи: Вам дан граф с выделенным множеством вершин $S$. Вам надо для каждой вершины графа узнать ближайшую к ней из $S$ и найти до неё расстояние.

Решение: снова добавляем в очередь пары $(s_i, s_i)$ и итерируемся, пока есть хотя бы одна непосещённая вершина(это можно сделать, например, поддерживая счётчик вершин, которые мы посетили).