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(від ближньої до далекої), і воно порожнє, коли дешевий маршрут до далекої клітинки проходить через ближню
