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

Материал из Algocode wiki
Перейти к: навигация, поиск
(Новая страница: «Идею с несколькими стартами в BFS можно применить для такой задачи: Вам дан граф с выделен...»)
 
Строка 1: Строка 1:
Идею с несколькими стартами в BFS можно применить для такой задачи:
+
==Задача==
 
Вам дан граф с выделенным множеством вершин $S$. Вам надо для каждой вершины графа узнать ближайшую к ней из $S$ и найти до неё расстояние.
 
Вам дан граф с выделенным множеством вершин $S$. Вам надо для каждой вершины графа узнать ближайшую к ней из $S$ и найти до неё расстояние.
  
Решение: снова добавляем в очередь пары $(s_i, s_i)$ и итерируемся, пока есть хотя бы одна непосещённая вершина(это можно сделать, например, поддерживая счётчик вершин, которые мы посетили).
+
==Идея==
 +
 
 +
Здесь есть несколько различных подходов :
 +
 
 +
Первый подход - сделать фейковую вершину $X$ и провести из нее ребра до всех вершин $S$, почему это будет работать, когда мы запустимся из $X$, то мы одновременно пометим все вершины из $S$, но это ровно то, что нам требуется
 +
 
 +
Заметим, что мы делаем одно лишнее действие, мы добавляем вершину $X$ в очередь, давайте сразу просто добавим в очередь все вершины из $S$
 +
 
 +
Теперь как же найти ближайшую из $S$ - можно либо честно восстановить путь по предкам и вывести из какой мы вершины пришли или просто добавлять в очередь пару $(s_{i}, s_{i})$, и при добавлении ребра из $x$ в $y$, добавлять в очередь пару $(y, num[x])$, где $num[x]$ - номер ближайшей к $x$ вершины из $S$

Версия 01:51, 19 ноября 2019

Задача

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

Идея

Здесь есть несколько различных подходов :

Первый подход - сделать фейковую вершину $X$ и провести из нее ребра до всех вершин $S$, почему это будет работать, когда мы запустимся из $X$, то мы одновременно пометим все вершины из $S$, но это ровно то, что нам требуется

Заметим, что мы делаем одно лишнее действие, мы добавляем вершину $X$ в очередь, давайте сразу просто добавим в очередь все вершины из $S$

Теперь как же найти ближайшую из $S$ - можно либо честно восстановить путь по предкам и вывести из какой мы вершины пришли или просто добавлять в очередь пару $(s_{i}, s_{i})$, и при добавлении ребра из $x$ в $y$, добавлять в очередь пару $(y, num[x])$, где $num[x]$ - номер ближайшей к $x$ вершины из $S$