ゼオスTTのブログ

気が向いた時に、主にプログラミング関係の記事を書くつもり。しかし気が向かない。

ワーシャル-フロイド法の経路復元

アルゴリズム

あまり記事を見かけない、ワーシャル-フロイド法の経路復元（もちろん O(|V|) のもの）を3種紹介。

以後、「更新処理」は次の(*)の部分に入るコードを指すものとする。

for (int k = 0; k < V; k++)
    for (int i = 0; i < V; i++)
        for (int j = 0; j < V; j++)
            if (d[i][k] + d[k][j] < d[i][j]) {
                d[i][j] = d[i][k] + d[k][j];
                // (*)
            }
            // (**)

方法1: 経由点を保存

k で更新したから k を保存する。至って普通の発想。

定義

via[i][j] := i から j への最短経路における経由点

初期化

全要素について、

via[i][j] = i;
更新処理
via[i][j] = k;
経路復元
void printPath1_aux(int begin, int end) {
    if (via[begin][end] == begin) {
        if (begin != end)
            printf("%d ", begin);
        return;
    }

    printPath1_aux(begin, via[begin][end]);
    printPath1_aux(via[begin][end], end);
}

void printPath1(int start, int goal) {
    printPath1_aux(start, via[start][goal]);
    printPath1_aux(via[start][goal], goal);
    printf("%d\n", goal);
}

printPath1_aux() は [begin, end) の範囲の経路を復元する。

まあ、経由点なんか保存しちゃったら、こうするしかないよね。。。
再帰呼出しの練習にでもどうぞ。

方法2: 1つ前の点を保存

せめてダイクストラ法みたいに逆から辿れると嬉しい。

定義

prev[i][j] := i から j への最短経路における j の1つ前の点

初期化

全要素について、

prev[i][j] = i;
更新処理
prev[i][j] = prev[k][j];
経路復元
int stack[MAX_V], sp;

void printPath2(int start, int goal) {
    sp = 0;
    for (int cur = goal; cur != start; cur = prev[start][cur])
        stack[sp++] = cur;
    stack[sp++] = start;

    while (sp--)
        printf("%d%c", stack[sp], " \n"[!sp]);
}

まんまダイクストラ法の経路復元。

だいぶ楽になった。

方法3: 1つ後の点を保存

やはりスタート地点から辿れるのが至高。

定義

next[i][j] := i から j への最短経路における i の1つ後の点

初期化

全要素について、

next[i][j] = j;
更新処理
next[i][j] = next[i][k];
経路復元
void printPath3(int start, int goal) {
    for (int cur = start; cur != goal; cur = next[cur][goal])
        printf("%d ", cur);
    printf("%d\n", goal);
}

フツーに前から復元していく。

全点対間の最短経路を求めるアルゴリズムだからこそ為せる業。
圧倒的に楽になった。

なお、冒頭のコードの(**)の部分に

else if (k != i && d[i][k] + d[k][j] == d[i][j])
    next[i][j] = min(next[i][j], next[i][k]);

と書き足してやることで、辞書順最小の経路を復元することもできる。


以上、あまり書かれていないのはおそらく常識すぎるからであろう、ワーシャル-フロイド法の経路復元でした。

方法1、嫌いじゃない。

（追記）

O(|V|^2) でよければ、更新前の d と同じ行列（＝隣接行列）g を用いて、次のように経路復元できる。

// ちなみにこれも辞書順最小の経路が復元できる
void printPath4(int start, int goal) {
	int cur = start;
	while (cur != goal) {
		printf("%d ", cur);

		for (int i = 0; i < V; i++)
			if (i != cur && g[cur][i] + d[i][goal] == d[cur][goal]) {
				cur = i;
				break;
			}
	}
	printf("%d\n", goal);
}

こちらは経路復元用に追加の情報を必要としないため、ワーシャル-フロイド法本体のコードが非常に簡潔になる（本来のあの簡潔さを保てると言うべきか）というメリットがある。また、経路復元自体もさほど複雑ではない。
さらに、ワーシャル-フロイド法が O(|V|^3) である以上、「全点対間の最短経路を求めよ」という問題*1でもない限り*2、経路復元が O(|V|^2) で困ることはない。
ゆえに、たいていの場合はこの書きやすい経路復元で事足りるため、上で紹介した O(|V|) の経路復元は出番がないかもしれない……。

はっ、もしやこれが、あまり記事を見かけない真の理由！？

*1:経路復元のオーダによって、解法は O(|V|^3) または O(|V|^4) となろう。

*2: O(|V|^4) が落ちて O(|V|^3) が通るとなると |V| \leq 2 \times 10^2 くらいの制約になるだろうが、 (2 \times 10^2)^3 \approx 10^7 回もの出力を行えば、それだけでTLEしてしまう。したがって、少なくともI/O処理のあるコンテストではそのような問題は出ないと思われる。