Почему dist инициализируют бесконечностью и как не словить переполнение при суммировании весов?
Видел, что dist всегда заполняют чем-то вроде 1e18 или INT_MAX. Почему именно бесконечностью, а не нулём? И почему говорят, что INT_MAX опасен — у меня Дейкстра иногда выдаёт отрицательные расстояния, хотя все веса положительные.
2 ответа
dist = «лучшее известное расстояние». В начале мы ничего не знаем, кроме dist[s] = 0, поэтому остальные = бесконечность (ещё недостижимы). Если поставить 0, релаксация dist[v] + w < dist[u] сломается: dist[u] уже 0, ничего не улучшится, все расстояния останутся 0.
Переполнение: если INF = INT_MAX и вы считаете dist[v] + w, где dist[v] == INF, то INT_MAX + w переполняет int и становится отрицательным числом — которое «меньше» любого dist[u], и алгоритм релаксирует мусором.
Правила безопасности:
using ll = long long;
const ll INF = 1e18; // НЕ LLONG_MAX!
// 1e18 + 1e18 ещё влезает в long long (макс ~9.2e18) без UB
// проверяй достижимость перед релаксацией:
if (dist[v] != INF && dist[v] + w < dist[u]) ...
Берут именно 1e18, а не LLONG_MAX, чтобы INF + INF не переполнилось.
Ещё одна тонкость: даже без INF сумма реальных весов пути может переполнить int. Если рёбер до 10^5 и вес до 10^4, путь весит до 10^9 — впритык к INT_MAX (~2.1·10^9), а если чуть больше — UB. Поэтому в задачах на пути по умолчанию берут long long для dist. Дешевле перестраховаться, чем ловить WA на максимальном тесте.