Math
Самый дешёвый путь
Местность, где шаг стоит цену клетки, в которую входишь, и волна закрытых вершин расходится по ЦЕНЕ, а не по расстоянию. Ползунок кладёт на карту отрицательное ребро, и у него три измеренных участка: права, ошибается, пути нет вовсе.
Что происходит
Шаг здесь стоит цену клетки, в которую входишь, поэтому волна закрытых вершин расходится не кругами: через дешёвую низину она уходит далеко, в дорогую гряду упирается. Эта картинка и есть вся разница между обходом в ширину и Дейкстрой. Пока веса неотрицательны, ответ доказуемо кратчайший, и проверяется он здесь Беллманом — Фордом до неподвижной точки — никогда вторым запуском того же алгоритма — да ещё полным перебором простых путей на маленьких сетках. На ровной местности цена имеет точный вид w(i + j): любой монотонный путь стоит одинаково. Счётчики тоже тождества: каждая вершина закрывается ровно один раз, каждое ребро релаксируется ровно один раз, и рёбер 4m(m−1). Дальше ползунок кладёт на карту одно направленное отрицательное ребро, и у него три участка, каждый измерен, а не описан. До −15 не ломается ничего: отрицательное ребро само по себе не беда. От −16 до −50 Дейкстра отвечает 93 там, где правда 92, потом 78, потом 58 — всегда БОЛЬШЕ, потому что закрытую вершину она не переоткрывает, — и рядом с жёлтым маршрутом появляется настоящий, чтобы ошибку было видно, а не объявлено. На −51 возникает отрицательный цикл: кратчайшего пути нет вовсе, Беллман — Форд это говорит, а Дейкстра печатает те же 93 с невозмутимым видом.
Уравнения модуля
Уравнения местность на сетке m x m, у каждой клетки цена 1..9, шаг стоит столько, сколько стоит клетка, в которую вы входите; старт вверху слева, цель внизу справа при неотрицательных весах алгоритм Дейкстры верен - проверено по алгоритму Беллмана-Форда, доведённому до неподвижной точки, а на 3x3 и 4x4 - по ПОЛНОМУ перебору простых путей у ровной местности есть замкнутая формула: стоимость до (i, j) = w(i + j), поэтому цель стоит w·2(m−1) - 120 при w = 5, m = 13 закрытых вершин = m² (каждая закрывается ровно один раз); релаксаций = рёбер = 4m(m−1) = 624 при m = 13; вставок в кучу 169 на местности по умолчанию по умолчанию 13x13, скидка выключена: самый дешёвый путь до цели 93, те же 93 по Беллману-Форду, 25 клеток в маршруте, 0 клеток, где они расходятся одно направленное ребро-скидка из (0,7) в (5,0), и у ползунка ТРИ режима, все измерены: вплоть до −15: ошибки нет совсем - отрицательное ребро само по себе не проблема от −16 до −50: Дейкстра выдаёт 93, тогда как на самом деле 92, 78, 58 - всегда СЛИШКОМ БОЛЬШОЕ значение, а ответы расходятся на 65, 122, 159 из 169 клеток −51 и ниже: отрицательный цикл - кратчайшего пути нет, Беллман-Форд это показывает, а Дейкстра всё равно печатает 93 концы ребра-скидки выбраны перебором всех пар: окну нужно d(дальней) − d(ближней) < k < cost(от ближней к дальней), и оно пусто, когда дешёвый путь к дальней клетке идёт через ближнюю
