ワーシャルフロイド法で求めた最短経路を復元する

自分用おぼえがき。

AtCoder Beginner Contest 143にて、ワーシャルフロイド法を用いて解く問題が出ましたが、そこで経路を復元すると回答が求まるんじゃないかと思って調べました。
実はこの問題では、経路復元では正しい回答は求まらなかったわけですが、せっかく調べたので供養の意味も込めて書き残しておきます。

前提

ワーシャルフロイド法自体はわかっているものとします。

方法

ワーシャルフロイド法で操作するグラフの操作前の状態を保存しておき、操作後の距離が入っているグラフと照らし合わせて経路を辿っていけばよいです。

// gが最短経路算出後のグラフ
// hが最短経路算出前のグラフ
vector<int> restore_path (int start, int end) {
    vector<int> p;
    int curr = start;
    while (curr != end) {
        // nは頂点数
        for (int i = 0; i < n; i++) {
            // (curr)---h[curr][i]---(i)---g[i][end]---(end)
            // と
            // (curr)-----------g[curr][end]-----------(end)
            // が一致すれば、iは最短経路に含まれる頂点である
            if (i != curr && h[curr][i] + g[i][end] == g[curr][end]) {
                curr = i;
                p.push_back(i);
                break;
            }
        }
    }
    return p;
}

参考

こちらのブログワーシャル-フロイド法の経路復元を参照させていただきました。