導入

前章では単一の頂点 \(s\) から他の全ての頂点への最短路を \(s\) を根とした最短路木を作ることで見つけるアルゴリズムについて議論しました。最短路木はグラフの各頂点 \(v\) に対して二つの情報を割り当てます:

この章で扱うのは、もっと一般的な全組最短路問題 (all pairs shortest path problem, APSP) です。これは任意のソース頂点から任意の目標頂点への最短路を求める問題であり、この問題を解くアルゴリズムは \(G\) の全ての頂点の組 \(u, v\) に対して次の情報を計算します:

この直観的な定義は二つの例外的なケースをいくつか無視していますが、どれも前章で見たものです:

全組最短路問題の出力は二つの \(V \times V\) の配列であり、一つには\(V^{2}\) 個の最短路の距離2が、もう一つには \(V^{2}\) 個の前者が格納されます。ですがこの章では、距離の配列を計算することに集中します。最短路を実際に構築するために必要になる前者配列は、アルゴリズムをほんの少し改変するだけで計算できます (ヒント、ヒント)。


  1. 正確には歩道 (walk) です。[return]

  2. 都市の間の距離を調べるのに印刷された道路地図を使っていた時代には、地図に三角形の “距離表” が付いていました。例えばシャンペーンとコロンバスの間の距離が知りたいときには、この表の “シャンペーン” の行と “コロンバス” の列の交点を調べます。[return]



Amazon.co.jp アソシエイト (広告)
Audible の無料体験を始めよう
amazon music unlimited で音楽聞き放題
The Art of Computer Programming Volume 1 Fundamental Algorithms
プログラミングコンテストチャレンジブック [第2版]
世界標準MIT教科書 Python言語によるプログラミングイントロダクション
アルゴリズムイントロダクション 第3版 総合版:世界標準MIT教科書