Non-Stop Travel 解説

アルゴリズムの概略

有向グラフが与えられて，「スタート地点からゴール地点までの最短経路を求めよ」という問題。 非常にシンプルな最短経路問題で，ダイクストラ法で効率的に解くことができます。

このような問題には，スタートからゴールまでの最短距離（最短時間）のみを求める問題と， その経路まで求める問題があります。 本問題は後者の方で，最短となる経路を出力しなければなりません （そのような経路は一般には複数ありますが，本問題ではそのような経路は一つしか存在しないことが保証されています）。

ダイクストラ法は頻出アルゴリズムなので別途ダイクストラ法の解説を用意していますから，詳しくはそちらを参照してください。 基本的なダイクストラ法を改造して経路も求められるようにするのは簡単で， 各ノードに対して「どこから辿ってきたか」を表す直前の経由ノードを記憶しておくだけで済みます。 ダイクストラ法が終了した時点で，ゴールノードから逆順にその情報を辿っていけば，最初のノードまでの逆順の経路が得られます。

アルゴリズムの実装

ここでは有向グラフなので，特別に隣接行列の表を作成する必要はなく，各ノードにそこから伸びるパスを持たせればいいでしょう。

また，確定ノードを求める方法として， 解答例では単純な実装（確定ノードを全ノードを調べて決める）と優先度付き待ち行列を用いた実装（C++のpriority_queueを使用）を載せています。 この問題では最大でもノード数 n = 10 で，単純な実装の方が速く動いてしまっていますが， ノード数が大きい問題では優先度付き待ち行列も効いてくるでしょう。

$Id: index.shtml 1335 2007-03-01 09:06:39Z SYSTEM $