経路・ビット・整列のアルゴリズム

要点と定義

アルゴリズムは、入力から目的の結果を得るための処理手順です。手順を追うときは、初期値、処理の順序、条件を満たしたときの更新を確認します。この節では、最短経路を求める方法、ビット列の操作、クイックソートを扱います。いずれも公式シラバスの「代表的なアルゴリズム」に含まれる基礎です。

ダイクストラ法の基本。 地点を頂点、地点間の経路を辺、距離を辺の重みと考えます。出発地から各地点までの「現在わかっている最短距離」を仮の距離として記録します。未確定の地点から仮の距離が最小の地点を選び、その距離を確定します。次に、選んだ地点に隣接する未確定地点について、選んだ地点を経由した距離が記録済みの仮の距離より短ければ、距離と直前の地点を更新します。これを繰り返す方法がダイクストラ法です。

仮の距離を更新する候補は、「出発地から選んだ地点までの確定距離」と「そこから隣接地点までの辺の距離」の和です。まだ経路が見つかっていない地点には、十分大きな値（∞）を置くことがあります。更新時に直前の地点も記録しておけば、目的地から直前地点をたどって経路を復元できます。

ビットごとの演算。 ビットごとのAND（論理積）は、両方のビットが1である位置だけを1にします。OR（論理和）は、どちらかが1の位置を1にします。XOR（排他的論理和）は、ビットが異なる位置を1にします。ビットを選択肢などに対応させれば、ANDで二つの集合に共通する項目を取り出し、ORで複数の集合をまとめられます。共通する項目数は、結果に含まれる1の個数を数えて求められます。

符号なしの値Aが正のとき、AとAから1を引いた値とのANDを取ると、Aの最も右にある1が消えます。この操作を0になるまで繰り返した回数は、元の値に含まれる1の個数です。たとえば、ビット列「101100」は、操作ごとに「101000」「100000」「000000」となり、1を3個含みます。Aが最初から0なら、繰返しは行わず個数は0です。

最も右の1だけを取り出すには、Aから1を引いた値とAのXORを取り、その結果と元のAとのANDを取ります。たとえばAが「00101000」のとき、Aから1を引いた値は「00100111」です。XORの結果は「00001111」となり、これをAとANDすると「00001000」だけが残ります。

クイックソート。 基準値（ピボット）を選び、データを基準値より小さい側と大きい側に分けます。分けた各グループにも同じ処理を繰り返し、これ以上分ける必要のない小さな範囲になったら処理を終えます。基準値による分割を繰り返して整列する方法です。

適用条件と例

ダイクストラ法の更新例を考えます。出発地から地点Aまでの確定距離が4で、Aから地点Bへの辺が3なら、A経由の候補距離は4＋3＝7です。Bの仮の距離が6なら、候補の方が長いため更新しません。一方、Aから地点Cへの辺が2で、Cの仮の距離が∞なら、候補は4＋2＝6です。Cの距離を6にし、直前地点をAと記録します。地点を確定する操作と、隣接地点の仮の距離を更新する操作を分けて追うと、各段階の配列を確かめやすくなります。

この確定方法を使える条件は、辺の重みが負でないことです。負の辺があると、いったん確定した地点に後からより短い経路が見つかる可能性があり、この手順では最短距離を保証できません。また、隣接していないことを表す値（たとえば−1）は辺の距離ではありません。隣接関係を確認してから、距離を加算します。到達不能な地点がある場合は、その地点の仮の距離が∞のまま残ります。