В чём идея алгоритма поиска k-го кратчайшего пути?
Нужно найти не просто кратчайший путь из s в t, а k-й по длине (пути могут повторять вершины). Например, 3-й по длине маршрут. Дейкстра даёт только первый. Какая идея за k-м кратчайшим путём?
2 ответа
Если пути могут повторять вершины (необязательно простые) — есть простое обобщение Дейкстры. Обычная Дейкстра «закрывает» вершину, найдя кратчайший путь до неё (1 раз). Для k-го кратчайшего разрешаем закрывать каждую вершину до k раз: ведём счётчик cnt[v], и когда вершина извлекается из кучи в i-й раз — это её i-е по длине расстояние.
vector<int> cnt(n, 0);
priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<>> pq;
pq.push({0, s});
ll ans = -1;
while (!pq.empty()) {
auto [d, v] = pq.top(); pq.pop();
if (cnt[v] >= k) continue;
cnt[v]++;
if (v == t && cnt[v] == k) { ans = d; break; }
for (auto [u, w] : g[v])
if (cnt[u] < k) pq.push({d + w, u});
}
Сложность O(k·E·log(k·E)) по времени. Когда t извлекается из кучи в k-й раз — это и есть k-й кратчайший путь.
Осторожно с постановкой: эта схема — для путей с повторениями вершин (walks). Если нужны именно простые k кратчайших путей (без повторов вершин), задача сложнее — нужен алгоритм Йена (Yen's), который многократно запускает Дейкстру, временно удаляя рёбра/вершины предыдущих путей, со сложностью около O(k·V·(E + V log V)). На большинстве олимпиадных задач имеют в виду версию с повторениями — там хватает обобщённой Дейкстры выше.