Информатика · объяснение и практика

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

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

Синие фигурные скобки держат между собой оранжевый квадрат.

В теме Графы и маршруты · Учебная карта

Главная мысль

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

Как улучшается предварительная оценка

Пусть рёбра S→А имеют вес 4, S→Б вес 1, Б→А вес 2. После обработки S оценки А = 4, Б = 1. Следующей фиксируется Б с меньшей оценкой. Путь через неё улучшает А до 1+2 = 3. Затем А фиксируется со стоимостью 3. Первое обнаружение вершины не обязательно сразу даёт окончательный кратчайший путь.

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

Почему отрицательное ребро ломает доказательство

Возьмём S→А вес 2, S→Б вес 5, Б→А вес −4. Обычная схема может зафиксировать А с 2 раньше Б. Но путь S→Б→А имеет стоимость 1 и обнаружится позже. Отрицательное ребро позволяет ещё не обработанному пути резко уменьшить стоимость уже выбранной вершины, нарушая основной аргумент окончательности.

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

Пример

S→А = 7, S→Б = 2, Б→А = 3. Чему равно кратчайшее расстояние до А?

Минимум прямого 7 и обхода 2+3 = 5 даёт 5. Все веса неотрицательны, поэтому стандартная гарантия Дейкстры применима.

Какие детали важны в реализации

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

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

От чтения к действию

А теперь — вы

Какое условие соответствует обычной гарантии алгоритма Дейкстры?

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

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

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

Нет отрицательных циклов — значит, Дейкстра всегда корректна?

Нет. Даже отдельное отрицательное ребро без циклов может нарушить стандартную гарантию.

Углублённый разбор

Дека для кратчайших путей с весами ноль и один

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

Перед началом: BFS; Релаксация ребра.

Дека хранит две соседние стоимости

В обычном BFS каждое ребро добавляет единицу, поэтому очередь естественно идёт по слоям. При весах 0 и 1 из вершины расстояния d можно получить только d и d+1. Улучшенную вершину через нулевое ребро помещают в начало деки, через единичное — в конец. Это сохраняет обработку ближайших доступных меток прежде более дальних.

Расстояния изначально равны бесконечности, кроме нуля у источника. Ребро u→v расслабляют, если d[u]+w<d[v]. Важно строгое улучшение: равные расстояния не должны бесконечно добавлять вершины на нулевом цикле. Для восстановления одного пути предшественник также меняется только при строгом уменьшении.

Обнаружение ещё не означает окончательный ответ

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

При хранении в деке пары(метка,вершина) старую запись можно пропустить, если метка уже отличается от текущей d[v]. Это помогает явно отделять устаревшие предложения от актуальной обработки. Списки соседей просматриваются при окончательной актуальной обработке, и для графа с 0/1 весами получается линейная стоимость по вершинам и рёбрам.

Ограничение весов является частью доказательства

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

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

Улучшение после первого обнаружения

Условие. Рёбра s→a:1,s→b:0,b→a:0,a→t:1,b→t:1. Найдите расстояния до a,b,t методом 0-1 BFS.

  1. После обработки s вершина a получает 1 и помещается назад, b получает 0 и помещается вперёд. Следующей обрабатывается b.
  2. Из b нулевое ребро улучшает a до 0, поэтому актуальная a ставится вперёд. Также t получает 1 и ставится назад.
  3. Обработка a даёт до t кандидат 0+1=1, равный уже известному. Повторного улучшения и смены предшественника не требуется.
  4. Устаревшая запись a с меткой 1 пропускается. Итог: d(a)=0,d(b)=0,d(t)=1; путь s,b,t подтверждает последний ответ.

Ответ. d(a)=0,d(b)=0,d(t)=1.

Проверка. Путь s,b,a имеет стоимость 0, хотя прямое ребро s,a весит 1. Любой путь к t содержит одно из двух входящих рёбер веса 1, поэтому расстояние до t не меньше единицы.

Где легко ошибиться. Не фиксируйте расстояние при первом добавлении вершины. Бесплатный переход может улучшить уже обнаруженную метку, и запрет такой релаксации превращает 0-1 BFS в неверный обычный BFS.

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

Каково кратчайшее расстояние от s до a в задаче?

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

Почему нулевой цикл не вызывает бесконечный цикл алгоритма?

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

Можно применить метод к весам 0 и 5?

После деления всех весов на 5 они станут 0 и 1, если это действительно общий положительный масштаб. Найденные расстояния затем умножают обратно. Для произвольной смеси 0,1,5 такой замены недостаточно.

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

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

  • Alex Li:0-1 BFS, original algorithm implementation

    Вебом прочитаны собственные пояснения и реализация автора: дека, помещение нулевых рёбер вперёд и единичных назад. Определение и конечная трасса главы подготовлены отдельно. Предварительный PDF латвийской олимпиады оказался недоступен и не заявляется прочитанным.

Минимаксный путь по самому тяжёлому ребру

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

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

Измените смысл метки до изменения формулы

Для пути P определим стоимость B(P)=max по его рёбрам w(e). Рассматриваем неотрицательные веса, а пустому пути от источника назначаем ноль. Лучшая метка вершины d[v] — минимальный возможный B(P). Продолжение через ребро u→v даёт кандидат max(d[u],w(u,v)), который сравнивают с прежней меткой v.

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

Пороговая достижимость даёт независимый сертификат

Путь с максимальным весом не больше T существует тогда и только тогда, когда цель достижима в подграфе рёбер с w≤T. Поэтому оптимум можно подтвердить двумя фактами: показать путь при T и доказать недостижимость при меньшем существенном пороге. Для конечного графа достаточно рассматривать имеющиеся веса, поскольку между ними набор допустимых рёбер не меняется.

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

Суммарная кратчайшая длина решает другую задачу

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

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

Самое тяжёлое ребро против суммы

Условие. Неориентированные рёбра AB=1,BD=6,AC=4,CD=4,BC=7. Найдите минимаксный путь A→D и сравните с минимумом суммы.

  1. Путь A,C,D имеет максимум 4 и сумму 8. Путь A,B,D имеет максимум 6 и сумму 7.
  2. При пороге T=4 подграф содержит AC и CD, поэтому D достижима из A.
  3. При любом T<4 доступно из A только ребро AB либо вообще нет рёбер; D недостижима. Это доказывает оптимальный максимум 4.
  4. Обычная кратчайшая сумма равна 7 по A,B,D, что показывает различие критериев. Минимаксный ответ выбирает путь с большей суммой 8.

Ответ. Минимаксный путь A,C,D с порогом 4; минимум суммы A,B,D со стоимостью 7.

Проверка. Перебор простых путей даёт максимумы 4,6,7 и суммы 8,7,12,17 для соответствующих вариантов. Ни один путь не достигает D на рёбрах строго легче 4.

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

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

Каков оптимальный минимаксный порог в задаче?

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

Что делать с отрицательными весами?

Минимаксная постановка возможна, но начальное значение пустого пути нужно согласовать, обычно берут −∞. В данной главе явно выбраны неотрицательные препятствия и источник с меткой 0.

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

Только если это дополнительный критерий условия. Сам по себе оптимальный максимум допускает несколько маршрутов с разной суммой и числом рёбер.

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

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

  • Åkerblom, Hoseini, Chehreghani: Online Learning of Network Bottlenecks via Minimax Paths

    Первичная статья MachineLearning112,131–150; вебом прочитан PDF-раздел 2.1 сопределением minimax, связью с MST и модификацией Дейкстры. Стохастическая модель статьи в данной детерминированной задаче не используется.

Какие рёбра входят хотя бы в один кратчайший путь

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

Перед началом: Кратчайшие расстояния; Обратный граф.

Сравните маршрут через ребро с глобальным оптимумом

Пусть все веса строго положительны, dₛ[u] — расстояние от s до u, dₜ[v] — расстояние от v до t и D=dₛ[t] конечно. Ребро u→v лежит хотя бы на одном кратчайшем пути тогда и только тогда, когда оба нужных расстояния конечны и dₛ[u]+w(u,v)+dₜ[v]=D. Любой кратчайший путь через ребро даёт необходимость равенства.

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

Сертификаты через каждое ребро
Реброdₛ[u]+w+dₜ[v]Равно D=5?
s→a0+2+3=5да
s→b0+1+4=5да
b→a1+1+3=5да
a→t2+3+0=5да
b→t1+5+0=6нет
s→t0+6+0=6нет

Второй запуск идёт по обращённым направлениям

Чтобы найти расстояния до t, строят граф с каждой стрелкой v→u того же веса вместо u→v и запускают алгоритм из t. Полученное расстояние до v равно исходному расстоянию v→t. Запуск из t без обращения рёбер решает другую задачу и в ориентированном графе обычно даёт неверный сертификат.

Недостижимые вершины обрабатывают отдельно: арифметическое выражение с бесконечностью не следует использовать как формальное равенство реальных длин. Если сама цель недостижима, кратчайшего s→t пути в данной постановке нет. Фильтр рёбер тогда должен сообщить этот статус, а не объявить все бесконечные равенства подходящими.

Нулевой цикл меняет формулировку результата

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

После отбора подходящих рёбер получается ориентированная структура, в которой расстояние от s строго растёт вдоль каждого ребра. Значит она ациклична. На ней можно считать количество кратчайших путей или анализировать обязательность рёбер, но равенство расстояний само по себе отвечает только на вопрос «хотя бы один», а не «каждый».

Отобрать все допустимые рёбра

Условие. Рёбра s→a:2,s→b:1,b→a:1,a→t:3,b→t:5,s→t:6. Найдите рёбра, лежащие хотя бы на одном кратчайшем s→t пути.

  1. Расстояния от s равны dₛ(s)=0,dₛ(b)=1,dₛ(a)=2,dₛ(t)=5.
  2. В обращённом графе получаем dₜ(t)=0,dₜ(a)=3,dₜ(b)=4,dₜ(s)=5.
  3. Для s→a,s→b,b→a,a→t суммы dₛ[u]+w+dₜ[v] равны 5. Все четыре ребра проходят проверку.
  4. Для b→t сумма 1+5+0=6, для s→t сумма 0+6+0=6. Они не входят ни в один кратчайший путь стоимости 5.

Ответ. Подходят s→a,s→b,b→a,a→t; не подходят b→t,s→t.

Проверка. Два кратчайших пути s,a,t и s,b,a,t имеют стоимость 5. Объединение их рёбер совпадает с результатом шести локальных проверок.

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

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

Какое ребро из перечисленных не входит в кратчайший путь задачи?

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

Почему нужен обратный граф, а не обратный порядок вершин?

Направления рёбер задают допустимое движение. Перестановка списка вершин не меняет стрелки и не превращает расстояние t→v в нужное v→t.

Как понять, что ребро обязательно?

Нужно дополнительно исследовать все оптимальные пути, например подсчитать их на отобранном DAG и сравнить число путей через ребро с общим числом. Одного равенства расстояний недостаточно.

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

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

  • James Aspnes, Yale: ShortestPath

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

Допустимая эвристика A* может требовать повторного открытия

Допустимая эвристика не завышает остаточную длину, но может нарушать локальное согласование по ребру. Тогда A* обязан разрешать улучшение уже раскрытого состояния и раскрывать его повторно. Закрытый список без переоткрытия способен вернуть неоптимальный путь даже при полностью допустимой эвристике.

Перед началом: Алгоритм Дейкстры; Нижняя оценка стоимости.

Два свойства эвристики отвечают на разные вопросы

Пусть конечный граф имеет неотрицательные длины и достижимую цель G. Допустимость означает 0≤h(v)≤dist(v,G), причём h(G)=0. Согласованность требует h(u)≤w(u,v)+h(v) на каждом ребре. Второе является локальным условием, из которого допустимость следует вдоль пути к цели. Обратное в общем случае неверно: отдельные нижние оценки могут плохо согласовываться между соседями.

A* хранит найденную длину префикса g(v) и выбирает минимальный f(v)=g(v)+h(v). При согласованной эвристике приведённые длины w+h(v)−h(u) неотрицательны, и действует свойство окончательности извлечённой метки, как у Дейкстры. Но при одной допустимости приведённое ребро может стать отрицательным. Поэтому первое раскрытие узла ещё не гарантирует оптимальность его g.

Улучшение закрытой вершины должно вернуться в очередь

Когда релаксация нашла строго меньший g(v), обновляем предка и метку. Если v уже была закрыта, переносим её обратно в OPEN. Повторное раскрытие распространяет улучшение дальше к цели. Останавливаемся при извлечении цели с минимальным актуальным f, а не при первом обнаружении ребра в неё. Устаревшие записи очереди должны пропускаться, иначе трасса может использовать прежний g.

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

Корректность не обещает отсутствия повторной работы

Несогласованная эвристика может быть полезной нижней оценкой, но приводить к многократным раскрытиям. Поэтому нельзя одновременно объявить её произвольно допустимой и применять оценку «каждая вершина раскрывается один раз». Это отдельный вопрос стоимости алгоритма. Для проверки правильности маленького примера надёжнее независимо перечислить простые пути, чем судить по числу посещённых узлов. Нулевые рёбра допустимы при строгом улучшении g, которое не создаёт бесконечных повторов одного и того же значения.

Ключевые раскрытия при переоткрытии
Раскрытый узелАктуальный gИзменение
S0A=3,B=1
A3G=5
B1A улучшается до2
A повторно2G улучшается до4
G4Оптимальная цель извлечена

Допустимая оценка требует второго раскрытия A

Условие. Дуги S→A=3,S→B=1,B→A=1,A→G=2,B→G=100. Эвристика h(S)=0,h(A)=0,h(B)=3,h(G)=0. Найдите ответ A* с переоткрытием и покажите ошибку запрета переоткрытия.

  1. Истинные остаточные длины из A и B равны 2 и3, поэтому все h допустимы. Но на B→A имеем 3>1+0, то есть согласованность нарушена.
  2. После раскрытия S очередь содержит A с g=3,f=3 и B с g=1,f=4. Сначала раскрываем A и получаем G с g=f=5.
  3. Затем раскрываем B и находим улучшение A до g=2,f=2. Если A навсегда закрыта, улучшение не проходит через A→G и цель будет извлечена со старой стоимостью 5.
  4. При корректном переоткрытии A снова раскрывается с g=2, улучшает G до4 и даёт путь S–B–A–G. Прямой перебор путей подтверждает оптимум 4.

Ответ. С переоткрытием ответ 4; запрет переоткрытия в описанной версии возвращает 5 и ошибается.

Проверка. Три простых S–G пути имеют стоимости 5,4,101. Истинные остаточные длины подтверждают допустимость, а конкретное ребро B→A независимо свидетельствует несогласованность.

Где легко ошибиться. Не заменяйте согласованность одной допустимостью при использовании окончательного CLOSED. Если закрытые состояния могут улучшаться, их новые метки нужно снова распространить.

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

Какова оптимальная длина S–G, найденная корректным A* с переоткрытием?

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

Можно ли остановиться при первом получении G с меткой 5?

Нет. В очереди ещё находится B с нижней оценкой 4, через которую получается более короткий путь. Цель должна быть извлечена как минимальный актуальный элемент после всех необходимых улучшений.

Почему h(B)=3 не является завышением?

От B до G есть путь B–A–G длины 1+2=3. Эвристика равна точной остаточной длине B, но соседняя h(A)=0 слишком слабая для локального согласования. Точность одной вершины не обеспечивает согласованность пары.

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

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

  • Felner et al.: Inconsistent Heuristics in Theory and Practice, §3–4

    Прочитаны admissibility/consistency и переоткрытие узлов CLOSED при улучшенном g; оценка числа повторных раскрытий относится к другим разделам и здесь не переносится. Собственная сеть S,A,B,G имеет точную трассу с ответами 4 и5; рисунки и веса статьи не переводились.

Целые ограниченные веса и кольцо корзин Дайла

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

Перед началом: Релаксация расстояний; Целочисленный остаток.

Минимальная метка движется только вперёд

Пусть веса лежат в {0,…,C}, C≥1. Дейкстра извлекает окончательные расстояния в неубывающем порядке. После извлечения текущего минимума d все конечные метки ещё не обработанных вершин лежат в [d,d+C]: старые были не больше предыдущего минимума плюс C, новые релаксации также не превосходят d+C. Поэтому одновременно нужны только C+1 последовательных целых ключей.

Метка k хранится в корзине с номером k mod(C+1). В окне длины C разные ключи не сталкиваются по модулю, так что циклический массив не смешивает разные актуальные расстояния. Указатель хранит полное расстояние, а не один остаток: иначе после оборота потеряется смысл номера. Пустые корзины пропускаются продвижением указателя вперёд.

Например, при C=4 корзина с индексом 1 обслуживает полные ключи 1,6,11 в разные моменты. Она не возвращает указатель к единице после обработки ключа 6. Индекс нужен для выбора физической очереди, а полный ключ — для порядка расстояний и отбраковки старых записей. Повторное использование памяти не означает повторного посещения того же расстояния.

Нулевое ребро остаётся в той же корзине

Релаксация веса 0 может добавить вершину с тем же d. Её нужно обработать до ухода из текущей корзины. Уменьшение метки перемещает вершину из прежней корзины в новую. Если реализация вместо удаления старой записи добавляет дубликат, при извлечении проверяется совпадение записанного ключа с текущей меткой и отсутствие окончательной обработки вершины. Старый кандидат не должен второй раз менять ответ.

При хранении одной записи на вершину с удалением по ссылке память равна O(n+C). При разрешённых дубликатах она может вырасти до O(m+C), поскольку каждое успешное улучшение оставляет старую запись. Временная оценка остаётся O(m+nC) при корректном прекращении после обработки достижимых вершин и пропуске устаревших кандидатов. Эти варианты нельзя смешивать в одной необъяснённой оценке памяти.

Маленький числовой вес важнее количества его битов

Кратчайший путь с неотрицательными весами можно выбрать простым, поэтому его длина не больше C(n−1). Указатель проходит O(nC) целых значений, а релаксации суммарно занимают O(m). При огромном C метод может проиграть обычной куче, даже если запись каждого веса короткая. Дробные или отрицательные веса не принадлежат заявленной модели корзин: произвольное округление меняет оптимальный путь, а отрицательность разрушает монотонность указателя.

Полные обороты, устаревшие записи и нулевой шаг

Условие. Ориентированный граф имеет дуги S→A=4, S→B=2, B→A=1, B→C=4, A→D=4, C→D=0, C→E=3, D→E=1, E→T=4, D→T=4. Других дуг нет. Возьмите C=4 и вариант с дубликатами. Найдите все расстояния от S, покажите повторное использование пяти корзин и обработку старых ключей.

  1. После S с ключом 0 получаем A=4 и B=2. Из B улучшаем A до 3 и открываем C с полным ключом 6, помещённым в корзину 6 mod 5=1. Это будущий оборот массива, а не расстояние 1.
  2. Из A с ключом 3 получаем D=7. При указателе 4 прежняя запись A=4 уже устарела и отбрасывается. Затем указатель проходит 5 и достигает полного расстояния 6.
  3. В корзине 1 извлекаем C=6. Нулевая дуга C→D улучшает D с 7 до 6 и добавляет её в ту же текущую корзину 1; C→E даёт предварительную E=9. Нельзя покинуть корзину до обработки добавленной D.
  4. Из D=6 получаем E=7 и T=10. Запись T хранится в корзине 0, которая раньше обслуживала S=0. При указателе 7 старая D=7 отбрасывается, а актуальная E=7 обрабатывается; её путь к T имеет длину 11 и не улучшает 10.
  5. При указателе 9 отбрасываем старую E=9. При 10 извлекаем T из повторно используемой корзины 0. Окончательные расстояния: S=0, B=2, A=3, C=6, D=6, E=7, T=10.

Ответ. Кратчайший путь к T: S–B–C–D–T длины 10. Полные ключи 6 и 10 используют корзины 1 и 0 после их предыдущего оборота; записи A=4, D=7, E=9 устарели.

Проверка. Независимый полный перебор простых путей и релаксации Беллмана–Форда дают тот же вектор расстояний. Путь S–B–A–D–T имеет длину 11, а ветвь через C–D имеет 10. Для D=6 свидетелем является S–B–C–D, включая нулевой последний шаг; проверка всех десяти дуговых неравенств подтверждает нижний сертификат расстояний.

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

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

После извлечения C с полным ключом 6 какая пара (индекс корзины D, новый полный ключ D) получается при релаксации нулевой дуги C→D?

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

Почему нужны C+1, а не C корзин?

Ключи d и d+C могут одновременно быть актуальными. По модулю C они совпадут, а по модулю C+1 различаются. Окно содержит C+1 целых значений, включая оба конца.

Подходит ли метод для весов только 0 и1?

Да, при C=1 он использует две корзины. Для этого специального случая очередь с добавлением в начало или конец даёт более привычный 0–1 BFS; Дайл обобщает идею на произвольную небольшую целую границу C.

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

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

  • Ted Ralphs: ISE411 Lecture9, Dial’s Implementation

    Прочитаны Properties1–2, C+1 корзин и O(m+nC) для неотрицательных целых длин. Собственная семивершинная трасса проверяет повторное использование корзин после оборота, нулевое продолжение в текущей корзине и три устаревших записи; вариант дубликатов отдельно оговорён по памяти.

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

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

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

Прямой и обратный поиск хранят разные расстояния

В конечной сети с неотрицательными весами запускаем прямой поиск от s и обратный от t. Для ориентированного графа обратный использует обращённые дуги, поэтому его метка d_b(v) оценивает путь именно от v до t. В каждом направлении отдельно поддерживаем очередь и множество окончательно обработанных вершин. Порядок чередования направлений может различаться, но внутри каждого извлекается собственный минимум.

Величина µ хранит стоимость лучшего реально собранного s–t маршрута. Она обновляется при соединении известных префикса и суффикса через общую вершину или ребро. В частности, при обработке ребра u→v с окончательным прямым u и обратным v проверяется d_f(u)+w(u,v)+d_b(v). Пока маршрут не найден, µ=∞. Каждая конечная кандидатная стоимость является верхней границей, даже если часть её меток ещё временная.

Сумма минимумов очередей закрывает оставшуюся возможность

Пусть α,β — минимальные актуальные ключи ещё не обработанных вершин двух очередей. Если µ конечно и α+β≥µ, можно остановиться. Предположим противное: есть оптимальный путь длины δ<µ. На нём возьмём первую не обработанную прямым поиском вершину v и её обработанного предшественника u. Для v истинный префикс не меньше α, значит её суффикс меньше β; поэтому v уже обработана обратным поиском.

Когда второе из событий обработки u и v произошло, пересекающее ребро было проверено и дало µ≤δ — противоречие. Если путь уже целиком обработан с прямой стороны, его цель тоже дала такую границу. В доказательстве важны обновления через пересекающие рёбра: одной произвольной общей вершины недостаточно. Устаревшие записи очередей нужно убрать перед чтением α и β.

Первая встреча может лежать на худшем маршруте

Поиски способны раньше обнаружить длинный путь из-за неравномерного распределения его стоимости. Поэтому ни общий отмеченный узел, ни первое ребро между фронтами сами по себе не дают нижней границы. Если одна очередь исчерпана, нужно отдельно использовать найденный конечный µ либо установить отсутствие пути; нельзя складывать случайные старые извлечённые ключи. Метод ускоряет некоторые запросы, но не обещает половину работы на любой сети.

Первая общая вершина даёт 10, оптимум равен 9

Условие. В неориентированном графе два пути между s,t: s–a–x–t с весами 3,3,3 и s–b–y–t с весами 1,1,8. Других рёбер нет. Проследите первую встречу и корректный сертификат остановки.

  1. После раскрытия s прямые метки равны a=3,b=1. После раскрытия t обратные метки x=3,y=8. Пока общей достигнутой внутренней вершины нет.
  2. Прямое раскрытие b с ключом 1 обнаруживает y с ключом 2. Это первая общая достигнутая вершина; её кандидат даёт 2+8=10, поэтому µ=10. Но минимумы очередей теперь 2 и3, их сумма 5<10: останавливаться рано.
  3. Продолжим прямой поиск: y с ключом 2 не улучшает 10, затем a с ключом 3 находит x с прямой меткой 6. Соединение через x даёт µ=6+3=9.
  4. Теперь минимальный прямой ключ 6, обратный 3. Их сумма 9 равна µ и удостоверяет остановку. Получаем путь s–a–x–t длины 9 вместо первого кандидата 10.

Ответ. Первая встреча даёт лишь верхнюю границу 10; точный ответ 9 сертифицирован равенством α+β=µ=9.

Проверка. Полный перебор простых s–t путей на этом цикле находит ровно две стоимости 9 и10. Сохранённые метки и порядок извлечения отдельно проверяются двумя обычными очередями Дейкстры.

Где легко ошибиться. Не останавливайтесь при первой общей достигнутой вершине. Храните лучший µ и сравнивайте его с суммой актуальных границ обоих направлений.

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

Какова истинная минимальная длина s–t в указанном графе?

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

Почему в обратном поиске ориентированные рёбра переворачиваются?

Иначе метка описывала бы путь t→v, а для склейки нужен v→t. В неориентированной сети различия нет, но в ориентированной это принципиально разные вопросы.

Обязательно ли расширять направления строго попеременно?

Нет. Можно выбирать их по размеру фронта или ключу, сохраняя корректность каждого отдельного поиска и правило остановки. Трасса примера специально продолжает прямую сторону, чтобы показать независимость доказательства от симметричного расписания.

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

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

  • Matthew Towers: Bidirectional Dijkstra

    Прочитаны ошибочность первой встречи, поддержание µ по пересекающимся поискам и доказательство остановки. Наш вариант использует минимумы ещё не извлечённых очередей; соответствующая нижняя граница доказана в тексте. Собственный цикл с путями 9 и10 проверен перебором. Princeton slides403 и retired MITlink не считаются прочитанным алгоритмом.

Δ-stepping: замыкание лёгких дуг перед тяжёлыми релаксациями

Δ-stepping ослабляет полный порядок извлечения Дейкстры: несколько близких меток обрабатываются одной корзиной. Внутри неё сначала многократно расслабляют лёгкие дуги, а тяжёлые откладывают до замыкания. Такое разделение позволяет объединять работу без предположения о маленьких целых весах.

Перед началом: Релаксация расстояний при неотрицательных весах; Диапазонная корзина приоритетной очереди.

Корзина задаёт диапазон, а не одно расстояние

Выберем Δ>0. Корзина B_i содержит текущие метки из [iΔ,(i+1)Δ). Дуги веса не больше Δ называем лёгкими, остальные тяжёлыми. В отличие от алгоритма Дайла, здесь допустимы неотрицательные вещественные веса, а одна корзина объединяет разные расстояния. Она не является остатком индекса по циклическому модулю.

Извлекают первую непустую корзину. Все её вершины обрабатывают по лёгким дугам, а новые или улучшенные метки того же диапазона возвращают в эту корзину. Пока она снова не опустеет, лёгкую обработку повторяют. Вершина может обрабатываться более одного раза, если её метка уменьшилась внутри диапазона.

Тяжёлые дуги используют уже замкнутые метки

Множество R запоминает все вершины, извлечённые при замыкании B_i. Лишь когда лёгкие релаксации больше не добавляют в неё работы, обрабатывают тяжёлые исходящие дуги всех вершин R, используя их последние метки. Тяжёлый переход из этого диапазона не может вернуться в него: его вес больше Δ.

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

Равные метки и нулевые циклы не создают улучшения

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

Выбор Δ влияет на количество параллельной работы и повторных релаксаций. Малые корзины усиливают упорядоченность, большие увеличивают внутреннее замыкание. Из определения алгоритма не следует безусловное ускорение на любом графе или любом оборудовании; здесь проверяется корректность диапазонов, порядка стадий и окончательных расстояний.

Лёгкий цикл и отложенные тяжёлые предложения

Условие. Возьмите Δ=3 и дуги s→u=2,s→w=8,u→v=1,v→u=0,u→w=3,v→x=2,w→x=0,x→t=6,w→t=4,s→t=20. Найдите расстояния и покажите две первые непустые корзины.

  1. В B₀ сначала находится s с меткой нуль. Лёгкая дуга открывает u с меткой два в той же корзине. Из u лёгкие дуги дают v=3,w=5 в B₁.
  2. После замыкания B₀ множество R={s,u}. Тяжёлое предложение s→w даёт восемь и не улучшает уже найденные пять; s→t временно даёт двадцать.
  3. В B₁ обрабатываются v=3,w=5. Из v появляется x=5 в той же корзине, поэтому нужна следующая лёгкая фаза. Дуги v→u и w→x не дают строгого улучшения.
  4. После полного замыкания R={v,w,x}. Тяжёлая дуга w→t предлагает девять, x→t — одиннадцать; остаётся t=9 в B₃.
  5. Окончательные расстояния: s=0,u=2,v=3,w=5,x=5,t=9. Путь s→u→w→t имеет длину девять; путь через x и тяжёлую дугу веса шесть длиннее.

Ответ. Замыкания дают R₀={s,u}, R₁={v,w,x}. Кратчайшее расстояние до t равно 9, а метки v,w,x принадлежат одному диапазону [3,6).

Проверка. Независимый алгоритм Беллмана — Форда проверяет все расстояния и неравенства по дугам. Наличие x в повторной лёгкой фазе подтверждает, что одноразовой обработки исходного содержимого B₁ недостаточно.

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

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

Какова метка t после тяжёлой стадии замкнутой корзины B₁?

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

Почему нулевая дуга v→u не вызывает бесконечность?

В этом примере он даже предлагает худшую метку u=3 вместо двух. В общем случае равная метка также не ставится повторно: работа добавляется только при строгом улучшении.

Чем этот пример отличается от кольца Дайла?

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

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

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

  • Meyer, Sanders: Δ-Stepping, ESA 1998

    Прочитан алгоритм на рис.1 с лёгкими весами ≤Δ, внутренним while и отложенными тяжёлыми запросами. Вероятностные оценки параллельной производительности не переносятся на пример. Граф с нулевой лёгкой дугой внутри лёгкого цикла и весь журнал корзин рассчитаны самостоятельно.

Минимальный средний вес цикла по формуле Карпа

Отрицательный цикл говорит, что стоимость повторяемого маршрута убывает без границы. Для сравнения скорости этого убывания нужна другая величина: сумма весов цикла, делённая на число рёбер. Формула Карпа находит минимальное среднее по таблице маршрутов точной длины. Она не выбирает просто самый отрицательный суммарный цикл и не подменяет точный слой лучшими маршрутами не более заданной длины.

Перед началом: Послойная динамика кратчайших маршрутов; Ориентированный цикл и сильная связность.

Нормировка по числу рёбер меняет задачу

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

Средний вес цикла C равен w(C)/|C|. Например, суммы −6 на шести рёбрах и −4 на двух дают средние −1 и −2: более отрицательная сумма не обязана давать меньшую скорость накопления стоимости. Минимальное среднее достаточно искать по простым циклам, поскольку среднее замкнутого маршрута является взвешенной по длинам смесью средних составляющих циклов.

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

Таблица считает ровно k рёбер

Выбираем старт s. Ставим F₀(s)=0, остальные F₀=∞. Для k от 1 до n используем F_k(v)=min(F_{k−1}(u)+w(u,v)) по входящим рёбрам. Пропускаем недостижимые значения. Старый слой хранится отдельно: добавление F_{k−1}(v) как кандидата изменило бы задачу на длину не более k.

Для каждой вершины с конечным F_n(v) вычисляем M(v)=max[(F_n(v)−F_k(v))/(n−k)] по 0≤k<n с конечным F_k(v). Теорема Карпа утверждает, что минимальное среднее равно min_v M(v). Сначала максимум по более ранним слоям одной вершины, затем минимум по вершинам; переставлять операции нельзя.

Почему формула реагирует именно на среднюю стоимость

Если вычесть одно число λ из каждого веса, маршрут длины k уменьшится на kλ, а каждая дробь формулы — ровно на λ. Средние циклов изменяются на ту же величину. При вычитании истинного минимального среднего отрицательных циклов уже нет, зато существует нулевой цикл. Это сводит доказательство формулы к случаю минимума ноль.

Таблица строится за O(n|E|), последующие сравнения дробей — за O(n²). Для рациональных данных их можно сравнивать точно перекрёстным умножением, избегая ложного порядка из округлений. Восстановление самого оптимального цикла требует дополнительного учёта маршрутов; вершина, минимизирующая формулу, сама по себе ещё не является полным списком рёбер цикла.

Отрицательное среднее из положительных и отрицательных шагов

Условие. Вершины 0,1,2,3. Рёбра 0→1:2, 1→2:−5, 2→0:1, 0→2:4, 2→3:1, 3→1:2, 3→3:0. Найдите минимальный средний вес цикла по Карпу со стартом 0.

  1. Граф сильно связен. Начальный слой равен [0,∞,∞,∞]. Для точных длин 1 и 2 получаем [∞,2,4,∞] и [5,∞,−3,5].
  2. Слои 3 и 4 равны [−2,7,9,−2] и [10,0,2,−2]. Например, F₄(1)=min(F₃(0)+2,F₃(3)+2)=0.
  3. Максимумы дробей для вершин 0,1,2,3 равны соответственно 12,−2/3,5/2,0. Для вершины 1 используются k=1,3: дроби −2/3 и −7, максимум −2/3.
  4. Минимум четырёх максимумов равен −2/3. Цикл 0→1→2→0 имеет сумму 2−5+1=−2 и длину 3, поэтому достигает этого среднего.

Ответ. Минимальный средний вес равен −2/3. Один достигающий цикл — 0→1→2→0.

Проверка. Независимый перебор простых ориентированных циклов даёт средние −2/3,5/2,−2/3,0. Сдвиг каждого веса на +2/3 делает все эти средние неотрицательными; предъявленный трёхрёберный цикл становится нулевым.

Где легко ошибиться. Не используйте в формуле слои «не более k рёбер». И не берите минимум дробей вместо максимума: для вершины 1 это ошибочно выбрало бы −7.

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

Чему равно минимальное среднее цикла в разобранном четырёхвершинном графе?

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

Может ли несколько циклов иметь одно минимальное среднее?

Да. В примере цикл 1→2→3→1 также имеет сумму −2 на трёх рёбрах. Формула определяет значение, а не обещает единственность достигающего цикла.

Нужно ли запрещать отрицательные рёбра?

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

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

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

  • Karp — A Characterization of the Minimum Cycle Mean, Theorem 1

    Формула min/max для маршрутов точной длины и перенос весов на константу. Четырёхвершинный граф, все слои и независимые циклы рассчитаны отдельно.

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться