Кратчайшее расстояние от всех вершин графа до выделенных: различия между версиями
Глеб (обсуждение | вклад) (Новая страница: «Идею с несколькими стартами в BFS можно применить для такой задачи: Вам дан граф с выделен...») |
Глеб (обсуждение | вклад) |
||
(не показана 1 промежуточная версия этого же участника) | |||
Строка 1: | Строка 1: | ||
− | + | ==Задача== | |
Вам дан граф с выделенным множеством вершин $S$. Вам надо для каждой вершины графа узнать ближайшую к ней из $S$ и найти до неё расстояние. | Вам дан граф с выделенным множеством вершин $S$. Вам надо для каждой вершины графа узнать ближайшую к ней из $S$ и найти до неё расстояние. | ||
− | + | ==Идея== | |
+ | |||
+ | Здесь есть несколько различных подходов : | ||
+ | |||
+ | Первый подход - сделать фейковую вершину $X$ и провести из нее ребра до всех вершин $S$, почему это будет работать, когда мы запустимся из $X$, то мы одновременно пометим все вершины из $S$, но это ровно то, что нам требуется | ||
+ | |||
+ | Заметим, что мы делаем одно лишнее действие, мы добавляем вершину $X$ в очередь, давайте сразу просто добавим в очередь все вершины из $S$ | ||
+ | |||
+ | Теперь как же найти ближайшую из $S$ - можно либо честно восстановить путь по предкам и вывести из какой мы вершины пришли или просто добавлять в очередь пару $(s_{i}, s_{i})$, и при добавлении ребра из $x$ в $y$, добавлять в очередь пару $(y, num[x])$, где $num[x]$ - номер ближайшей к $x$ вершины из $S$ | ||
+ | |||
+ | {{Автор|Глеб Лобанов|glebodin}} | ||
+ | {{Автор|Александр Гришутин|rationalex}} |
Текущая версия на 22:51, 18 ноября 2019
Задача
Вам дан граф с выделенным множеством вершин $S$. Вам надо для каждой вершины графа узнать ближайшую к ней из $S$ и найти до неё расстояние.
Идея
Здесь есть несколько различных подходов :
Первый подход - сделать фейковую вершину $X$ и провести из нее ребра до всех вершин $S$, почему это будет работать, когда мы запустимся из $X$, то мы одновременно пометим все вершины из $S$, но это ровно то, что нам требуется
Заметим, что мы делаем одно лишнее действие, мы добавляем вершину $X$ в очередь, давайте сразу просто добавим в очередь все вершины из $S$
Теперь как же найти ближайшую из $S$ - можно либо честно восстановить путь по предкам и вывести из какой мы вершины пришли или просто добавлять в очередь пару $(s_{i}, s_{i})$, и при добавлении ребра из $x$ в $y$, добавлять в очередь пару $(y, num[x])$, где $num[x]$ - номер ближайшей к $x$ вершины из $S$
Автор конспекта: Глеб Лобанов
По всем вопросам пишите в telegram @glebodin
Автор конспекта: Александр Гришутин
По всем вопросам пишите в telegram @rationalex