経路復元
(library/graph/route_restore.hpp)

• View this file on GitHub
• Last update: 2026-01-07 21:05:45+09:00
• Include: #include "library/graph/route_restore.hpp"

経路復元

できること

• 経路を復元する

計算量

$O(L)$

• L: パスの長さ

使い方

auto [dis, route] = dijkstra(G, {s});
vector<int> pth = route_restore(route, goal);

Verified with

• グラフ - 経路復元のテスト (tests/graph.route_restore.test.cpp)

Code

#pragma once
vector<int> route_restore(const vector<int> &route, int goal) {
    vector<int> path = {goal};
    while (!!~route[path.back()]) path.push_back(route[path.back()]);
    reverse(path.begin(), path.end());
    return path;
}

#line 2 "library/graph/route_restore.hpp"
vector<int> route_restore(const vector<int> &route, int goal) {
    vector<int> path = {goal};
    while (!!~route[path.back()]) path.push_back(route[path.back()]);
    reverse(path.begin(), path.end());
    return path;
}

Back to top page