Restore path
(graph/restore_path.hpp)

• View this file on GitHub
• Last update: 2024-07-31 17:14:51+09:00
• Include: #include "graph/restore_path.hpp"

使い方

s から t への最短路を求めたあと, パス上の頂点列を s -> ... -> t の順に std::vector<int> に格納して求める

Graph<T> g;
std::vector<int> s = {0};   // 始点の集合
const T INF;
auto [dist, par, root] = dijkstra(g, s, INF);
auto path = restore_path(par, t);

参考文献

Required by

• Tree Diameter (木の直径) (graph/tree_diameter.hpp)

Verified with

• verify/graph/dijkstra_2.test.cpp
• verify/graph/tree_diameter_1.test.cpp
• verify/graph/tree_diameter_2.test.cpp
• verify/graph/zero_one_bfs.test.cpp

Code

#pragma once

#include <vector>
#include <algorithm>

// restore path from root[t] to t
std::vector<int> restore_path(std::vector<int>& par, int t) {
    std::vector<int> path = {t};
    while (par[path.back()] != -1) path.emplace_back(par[path.back()]);
    std::reverse(path.begin(), path.end());
    return path;
}

#line 2 "graph/restore_path.hpp"

#include <vector>
#include <algorithm>

// restore path from root[t] to t
std::vector<int> restore_path(std::vector<int>& par, int t) {
    std::vector<int> path = {t};
    while (par[path.back()] != -1) path.emplace_back(par[path.back()]);
    std::reverse(path.begin(), path.end());
    return path;
}

Back to top page