Как восстановить сам кратчайший путь, а не только его длину (массив предков)?
Дейкстра/BFS считают расстояния, но в задаче нужно вывести сами вершины пути от s до t. Как восстановить маршрут? Понимаю, что нужно что-то запоминать при релаксации, но не соображу как.
2 ответа
Заводим массив parent[]: когда улучшаем dist[u] через вершину v, запоминаем parent[u] = v. После работы алгоритма идём от t по предкам до s и разворачиваем.
vector<int> parent(n, -1);
// внутри релаксации:
// dist[u] = dist[v] + w;
// parent[u] = v;
// pq.push({dist[u], u});
// восстановление:
vector<int> path;
if (dist[t] != INF) {
for (int v = t; v != -1; v = parent[v]) path.push_back(v);
reverse(path.begin(), path.end());
}
// path = последовательность вершин от s до t
Добавляет O(V) памяти и O(длины пути) на восстановление — асимптотика основного алгоритма не меняется. Работает одинаково для BFS, Дейкстры, Беллмана-Форда, DAG-релаксации.
Частая ошибка — записывать parent[u] до проверки, что путь реально улучшился. Обновлять parent нужно строго внутри того же if, где обновляется dist. Ещё: если путь недостижим (dist[t] == INF), цикла восстановления делать не надо — иначе зациклитесь или выведете мусор. Для Флойда-Уоршелла восстановление другое: хранят next[i][j] — первую вершину на пути из i в j, и обновляют next[i][j] = next[i][k] при релаксации через k.