Алгоритмы на графах: представление, пути и зависимости

Выбор представления графа, условия алгоритма Дейкстры, топологический порядок и длиннейший путь в DAG: сравнение задач и гарантий алгоритмов.

Задачи модуля

Начните с сохранения самой модели: направления, нулевого веса, изолированных вершин и нужных операций. Представление графа влияет и на память, и на стоимость обхода.

Далее сопоставьте три разные задачи: минимальную стоимость пути, порядок зависимостей и максимальную сумму в DAG. Ограничения на веса и циклы выводятся из логики каждого алгоритма.

  • Выбирать список или матрицу смежности по плотности графа и операциям, сохраняя направление и допустимый нулевой вес.
  • Выполнять релаксации Дейкстры и объяснять, почему отсутствие отрицательных циклов не заменяет неотрицательность рёбер.
  • Строить и проверять топологический порядок, затем вычислять длиннейший путь из заданного старта в DAG с учётом недостижимости.

Алгоритмы на графах

BFS: число кратчайших путей вместе с расстоянием

Первое посещение вершины фиксирует кратчайшее расстояние в невзвешенном графе, но не обязательно все кратчайшие маршруты. Другие вершины того же предыдущего слоя могут добавить новые способы добраться за столько же шагов.

Перед началом: Очередь; Ориентированный граф.

Слой задаёт допустимую длину

Поиск в ширину обрабатывает вершины по неубывающему расстоянию от источника. При первом обнаружении v через u назначают d[v]=d[u]+1. Для подсчёта путей добавляют c[source]=1. Первый кратчайший предшественник передаёт c[u], а каждый последующий предшественник с тем же равенством расстояний добавляет свой вклад. Рёбра из более далёкого слоя и рёбра, не увеличивающие расстояние ровно на единицу, в этот счёт не входят.

Не прекращайте работу после обнаружения цели

Если цель только что поставлена в очередь, ещё не все вершины предыдущего слоя могли быть обработаны. Остановка в этот момент может вернуть правильное расстояние и неправильное количество. Безопасно завершать после обработки всех нужных предшественников либо просто выполнить обычный BFS полностью. В графе с параллельными рёбрами заранее договоритесь, считаются ли различными пути по рёбрам или только последовательности вершин. В первом случае одинаковые переходы с разными идентификаторами добавляют отдельные способы.

Подсчёт является динамикой по слоям

Рёбра, участвующие в кратчайших путях, образуют ациклический слоистый граф, даже если исходный граф содержит циклы. Поэтому сумма вкладов корректна и не требует обхода всех маршрутов. Количество путей может быть экспоненциальным по размеру графа, так что тип целых чисел или выбранный модуль входит в постановку. Подсчёт по модулю сохраняет остаток, но не точное количество. Независимая проверка маленького примера — перечислить только маршруты найденной минимальной длины.

Для недостижимой вершины счётчик остаётся нулевым, а расстояние — бесконечным. Источник имеет один пустой кратчайший путь к себе.

Три способа длины три

Условие. Рёбра: s→a, s→b, a→c, a→d, b→c, c→t, d→t. Найдите расстояние и число кратчайших путей до t.

Три кратчайших пути из s в t Ориентированные рёбра: s в a и b; a в c и d; b в c; c и d в t. Каждый путь до t содержит три ребра. sabcdt
До c ведут два кратчайших пути, до d — один. Последний шаг в t складывает эти количества: 2 + 1 = 3.
  1. Первый слой содержит a,b с расстоянием 1 и счётчиками 1.
  2. Второй слой: c получает два вклада от a,b, d один от a.
  3. Обе вершины c,d ведут в t на расстоянии 3.
  4. Счётчик t равен 2+1=3: маршруты sact, sbct, sadt.

Ответ. d[t]=3, c[t]=3.

Проверка. Любой путь в t заканчивается через c или d, а они достижимы не раньше второго слоя; более короткого маршрута нет.

Где легко ошибиться. Повторное достижение уже посещённой вершины нельзя всегда игнорировать: при том же кратчайшем расстоянии оно добавляет новые пути.

Проверьте понимание

При d[v]=d[u]+1 новый кратчайший предшественник должен

Вопросы к этой главе

Почему циклы не дают бесконечный счёт?

В расчёт входят только рёбра, увеличивающие расстояние на единицу; вернуться в прежний слой нельзя.

Можно ли использовать ту же формулу с весами?

Нужен другой алгоритм расстояний и аккуратная обработка нулевых циклов. Обычный BFS предполагает одинаковую стоимость каждого ребра.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • MIT 6.006, лекция 9: Breadth-First Search

    Лекция 9: слои BFS и кратчайшие расстояния; счётчик путей добавлен с доказанным слоистым инвариантом. Проверены релевантные определения и условия, а не прочитан весь учебник. Условия задач и расчёты главы подготовлены отдельно.

Критический путь: раннее начало и запас задачи

Длительность проекта определяется не суммой всех работ, а самым длинным зависимым маршрутом. Чтобы найти запас отдельной задачи, нужны прямой и обратный проходы, а не только один максимальный путь.

Перед началом: Топологический порядок; Длительность работы.

Раннее начало использует максимум предшественников

Пусть каждая вершина DAG — работа с неотрицательной длительностью. Раннее начало ES равно максимуму ранних окончаний предшественников, а EF=ES+duration. Для вершин без предшественников ES=0. Топологический порядок гарантирует, что необходимые значения уже известны. Если независимые работы могут выполняться параллельно без ограничения ресурсов, длительность проекта равна максимальному EF среди конечных работ. Ограниченный штат или станок меняют задачу и требуют дополнительных ресурсных условий.

Обратный проход определяет поздние сроки

Задайте общий срок T, равный найденной минимальной длительности. У конечных работ позднее окончание LF=T. Для остальных LF равно минимуму поздних начал последователей, затем LS=LF−duration. Обратный топологический порядок обеспечивает готовность данных. Полный запас равен LS−ES. Нулевой запас отмечает критические работы, задержка которых без компенсации увеличивает срок проекта. Критических путей может быть несколько, поэтому хранить только одного предшественника недостаточно для полной карты запасов.

Проверяйте достижимость и смысл срока

Если граф содержит несвязанные компоненты, общий виртуальный конец позволяет согласовать их с одним сроком. Изолированная короткая работа может иметь большой запас, хотя у неё нет последователей. Отрицательный запас появляется при внешнем сроке меньше минимальной длительности и означает невозможность выполнить план в принятой модели. Это не отрицательная физическая длительность. Для проверки можно вручную составить расписание ранних начал и убедиться, что каждая зависимость соблюдена, а затем попробовать сдвинуть некритическую работу на её запас.

Наличие цикла зависимостей делает топологический порядок невозможным. Перед расчётом сроков это следует обнаружить, а не молча оставить часть работ необработанной.

Одна работа ждёт другую ветку

Условие. Длительности A=2,B=5,C=3,D=4; зависимости A→C,B→C,C→D. Найдите срок и запасы.

  1. A,B начинаются в 0 и заканчиваются в 2 и 5.
  2. C начинает в 5, заканчивает в 8; D занимает [8,12], срок T=12.
  3. Назад: LS(D)=8, LS(C)=5; A должна закончить к 5, значит LS(A)=3.
  4. Для B позднее начало 0. Запасы: A=3, B=C=D=0.

Ответ. Проект длится 12; только A имеет запас 3.

Проверка. Сдвиг A на [3,5] не меняет C. Задержка B на единицу сдвигает C,D и общий срок на единицу.

Где легко ошибиться. Алгоритм критического пути предполагает возможность параллельного выполнения независимых работ; ресурсное ограничение нельзя добавлять только в интерпретацию ответа.

Проверьте понимание

Нулевой полный запас означает

Вопросы к этой главе

Почему прямой проход берёт максимум?

Работа обязана дождаться всех предшественников, поэтому решает самый поздний из них.

Почему обратный проход берёт минимум?

Предшественник должен успеть ко всем последователям, значит ограничивает самый ранний их поздний старт.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • Jeff Erickson: Algorithms, глава 3 Dynamic Programming

    Динамика по ациклическим зависимостям; ранние и поздние сроки собственной модели выведены отдельно. Проверены релевантные определения и условия, а не прочитан весь учебник. Условия задач и расчёты главы подготовлены отдельно.

Компоненты сильной связности: сжать циклы без потери достижимости

Внутри сильно связной компоненты каждая вершина достижима из каждой. Сжатие таких блоков удаляет циклическую внутреннюю структуру и оставляет DAG зависимостей между блоками.

Перед началом: Достижимость; Ориентированный цикл.

Взаимная достижимость задаёт разбиение

Отношение «u достигает v и v достигает u» рефлексивно, симметрично и транзитивно. Поэтому вершины распадаются на непересекающиеся классы, называемые компонентами сильной связности. Ребро в одну сторону не объединяет классы: нужен обратный маршрут, который может состоять из нескольких рёбер. Изолированная вершина тоже образует компоненту, даже если у неё нет петли. Компонента не обязана быть полным подграфом или одним простым циклом.

Конденсация не может содержать цикл

Создадим по вершине на компоненту и проведём ребро при наличии исходного перехода между разными компонентами. Если бы в таком графе возник цикл, все его компоненты были бы взаимно достижимы и должны были бы объединиться. Полученное противоречие доказывает ацикличность. Внутренние рёбра и петли при построении конденсации удаляют, повторные межкомпонентные рёбра можно объединить. Достижимость между блоками сохраняется, но количество исходных маршрутов и расстояния сжатием не сохраняются автоматически.

Сертификат разбиения имеет две стороны

Нужно подтвердить сильную связность каждого блока и отсутствие взаимной достижимости между разными блоками. В маленьком графе достаточно путей внутри и топологического порядка конденсации. В больших применяют алгоритмы Косарайю или Тарьяна с линейной сложностью. Топологический порядок блоков полезен для анализа зависимостей с циклическими группами: сначала решают внутреннюю задачу компоненты, затем передают результат дальше. Он не превращает внутренние циклы в безопасные или разрешимые сами по себе.

При сжатии можно хранить отображение каждой исходной вершины в номер блока. Тогда любой запрос между вершинами переводится в запрос достижимости соответствующих блоков без потери смысла.

Три блока одного графа

Условие. Рёбра a↔b, b→c, c↔d, d→e. Найдите компоненты и конденсацию.

  1. a,b взаимно достижимы напрямую и образуют U={a,b}.
  2. c,d образуют V={c,d}; e остаётся W={e}.
  3. Обратных путей из V в U и из W в V нет, поэтому объединения невозможны.
  4. Конденсация имеет рёбра U→V и V→W, порядок U,V,W топологический.

Ответ. Компоненты {a,b}, {c,d}, {e}; конденсация — цепь из трёх вершин.

Проверка. Полный перебор достижимости по пяти вершинам даёт именно эти классы взаимности; e достижима из всех, но не достигает другие.

Где легко ошибиться. Вершина, достижимая из всех остальных, не обязана лежать с ними в одной сильной компоненте: обратная достижимость обязательна.

Проверьте понимание

Если конденсация содержит ориентированный цикл, значит

Вопросы к этой главе

Сохраняется ли длина кратчайшего пути?

Нет. Внутренние переходы блока исчезают; для расстояний нужна дополнительная информация.

Почему одиночная вершина сильносвязна?

Путь длины нуль ведёт из неё в себя, что достаточно для рефлексивной достижимости.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • Jeff Erickson: Algorithms, глава 6 Depth-First Search

    Раздел о сильных компонентах и DFS; ацикличность конденсации доказана через взаимную достижимость. Проверены релевантные определения и условия, а не прочитан весь учебник. Условия задач и расчёты главы подготовлены отдельно.

Потенциалы: отрицательные рёбра можно перевзвесить

Добавление разности потенциалов концов ребра меняет веса отдельных переходов, но все пути с одинаковыми концами сдвигает на одну величину. Это позволяет сделать веса неотрицательными и корректно применить Дейкстру.

Перед началом: Кратчайшие пути; Потенциальная функция.

Телескопическая сумма сохраняет сравнение путей

Определим w′(u,v)=w(u,v)+h(u)−h(v). На пути из s в t внутренние потенциалы сокращаются, поэтому новый вес равен старому плюс h(s)−h(t). Все пути между фиксированными концами получают одинаковую поправку и сохраняют порядок по стоимости. Для цикла поправка нулевая. Следовательно, отрицательный цикл перевзвешиванием не исчезнет; если он мешает исходной задаче, его нужно обнаружить отдельно.

Допустимый потенциал проверяется по каждому ребру

Для применения Дейкстры необходимо w′≥0 на всех обрабатываемых рёбрах. Потенциалы кратчайших расстояний от добавленного источника дают это свойство при отсутствии отрицательных циклов, но в небольшом примере можно просто предъявить h и проверить неравенства. После поиска расстояний возвращают исходные значения формулой d(s,t)=d′(s,t)−h(s)+h(t). Знаки поправки следуют из суммы пути; запоминать их без вывода опасно.

Алгоритм и сертификат разделяются

Готовый потенциал является коротким свидетельством неотрицательности новых весов. Найденный путь даёт верхнюю оценку расстояния, а корректный поиск в перевзвешенном графе устанавливает минимальность. Для недостижимой вершины расстояние остаётся бесконечным; конечный потенциал не создаёт маршрут. Нельзя запускать Дейкстру на исходных отрицательных рёбрах и лишь потом исправить ответ потенциалом: перевзвешивание должно предшествовать выбору вершин алгоритмом.

В примере потенциал b отрицателен, хотя все новые рёбра неотрицательны. Это нормально: ограничены разности потенциалов относительно весов, а не их абсолютные знаки. Прибавление одной константы ко всем h ничего не меняет. Следовательно, проверять «положительность потенциала» вместо неотрицательности перевзвешенных рёбер бессмысленно. На практике удобно сохранить таблицу старых весов, двух потенциалов и нового веса для каждого ребра; такой локальный реестр позволяет независимо проверить применимость Дейкстры до запуска поиска.

Отрицательное ребро без отрицательного цикла

Условие. Рёбра s→a=2,s→b=5,a→b=−4,b→t=3,a→t=6. Возьмите h(s)=h(a)=0,h(b)=−4,h(t)=−1.

  1. Новые веса по перечисленному порядку: 2,9,0,0,7; все неотрицательны.
  2. В новом графе кратчайший путь s→a→b→t имеет вес 2.
  3. Возвращаем исходное расстояние: 2−0+(−1)=1.
  4. Исходная сумма того же пути равна 2−4+3=1; другие варианты дают 8.

Ответ. Кратчайшее исходное расстояние до t равно 1, путь s,a,b,t.

Проверка. Граф ацикличен; перебор всех трёх путей до t даёт веса 1,8,8 и независимо подтверждает минимум.

Где легко ошибиться. Потенциал не устраняет отрицательный цикл: сумма поправок на замкнутом обходе всегда нулевая.

Проверьте понимание

Для цикла сумма новых весов относительно старых

Вопросы к этой главе

Может ли новый путь стать короче другого с теми же концами?

Их разность весов не меняется, поэтому относительный порядок сохраняется.

Зачем проверять все рёбра?

Одного оставшегося отрицательного веса достаточно, чтобы стандартное доказательство Дейкстры перестало применяться.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • MIT 6.006, лекция 14: Johnson’s Algorithm

    Лекция 14: неотрицательные перевзвешенные рёбра и восстановление расстояний через потенциалы. Проверены релевантные определения и условия, а не прочитан весь учебник. Условия задач и расчёты главы подготовлены отдельно.

Связанные методы

Когда список смежности выгоднее матрицы

Списки смежности хранят существующие соседства и обычно требуют O(V+E) памяти. Матрица резервирует O(V²) ячеек, зато позволяет быстро проверить заданную пару вершин. Выбор зависит от плотности графа и операций.

Разобрать с примером

Почему алгоритму Дейкстры нужны неотрицательные веса

Алгоритм Дейкстры последовательно фиксирует вершину с минимальной текущей оценкой расстояния и улучшает оценки соседей. Обычная гарантия корректности требует неотрицательных весов рёбер. Отсутствие отрицательного цикла само по себе недостаточно.

Разобрать с примером

Как порядок без входящих рёбер решает зависимости в ациклическом графе

Для зависимостей «сначала А, затем Б» топологический порядок ставит А раньше Б. В ориентированном графе без циклов такой порядок существует. Можно последовательно выбирать вершины, у которых не осталось входящих рёбер из ещё не обработанной части.

Разобрать с примером

Темы по порядку

  1. Когда список смежности выгоднее матрицыСравниваем список смежности и матрицу по памяти и операциям, сохраняем направление и вес рёбер и выбираем структуру под разреженность и требуемые запросы.
  2. Почему алгоритму Дейкстры нужны неотрицательные весаНаходим кратчайшие стоимости при неотрицательных весах, различаем предварительную оценку и окончательную вершину и показываем точную причину ограничения на отрицательные рёбра.
  3. Как порядок без входящих рёбер решает зависимости в ациклическом графеРазберите зависимости по входящим рёбрам: выберите доступный шаг, обновите счётчики и отличите допустимый порядок от расписания с длительностями.
  4. Длиннейший путь в DAG: когда работает топологический порядокМаксимальная сумма весов в DAG: фиксированный старт, недостижимые вершины, отрицательные рёбра и обновления в топологическом порядке.
  5. Остаточная сеть: зачем потоку обратные рёбраОстаточная сеть потока: свободная пропускная способность, обратное ребро как отмена и увеличение по узкому месту пути.
  6. Точка сочленения: когда удаление вершины разделяет графТочки сочленения: удаление вершины со связями, особое правило корня DFS и отличие от мостового ребра.
  7. Число путей в DAG: складываем способы, а не длиныКоличество путей в ациклическом графе: сумма способов прийти к предшественникам, общий хвост и начальная единица в источнике.
  8. Как система непересекающихся множеств поддерживает компоненты связностиПроследите объединение компонент через корни деревьев: почему find сравнивает представителей, а не непосредственных родителей, и когда обычной DSU недостаточно.

Проверьте понимание

Какой размер полной матрицы смежности для 10 вершин?

Рассчитать и проверить

Частые вопросы

Матрица всегда экономнее списка?

Нет. При разреженном графе её V² ячеек могут быть намного больше числа существующих рёбер.

Дейкстра запрещает нулевые веса?

Нет. Требуются неотрицательные, поэтому 0 допустим.

Почему могут получиться разные правильные списки?

Некоторые задачи не связаны требованиями порядка. Их можно переставлять, если каждое ребро по-прежнему направлено от более ранней позиции к более поздней.