1 経路の基本概念
1.1 グラフにおける経路の定義
グラフの文脈で「経路」とは、頂点の集合の中で、隣接関係（辺）に従って連なっていく一連の頂点（または辺）の並びを指す。通常、隣り合う2つの頂点が同一の辺で結ばれているとき、それらは経路を構成する隣接要素として扱われる。経路は到達可能性や連結性の基礎語となり、最短経路問題では、到達するまでのコストを比較する対象として使われる。
経路の定義では、方向（有向か無向か）、重複の許否、長さの定義の仕方が重要になる。これらは後述するアルゴリズムの正しさや計算量に影響するため、同じ「経路」という語でも条件設定が異なると結論も変わり得る。
1.2 経路の表し方
1.2.1 頂点列としての表現
経路を頂点列として表す場合、頂点の列 \(v_0, v_1, \dots, v_k\) の形で与える。ここで各 \(i\)（\(0 \le i < k\)）について、隣接する \(v_i\) と \(v_{i+1}\) の間に対応する辺が存在するなら、その頂点列は経路となる。有向グラフの場合は、辺が \(v_i \to v_{i+1}\) の向きで存在することが必要である。
頂点列の表現は直観的で、探索や復元（どの順で移動したか）を説明する場面で扱いやすい。特に経路の「始点」「終点」「通過順」の概念が明確にできる。
1.2.2 辺列としての表現
経路を辺列として表す場合、辺の列 \(e_1, e_2, \dots, e_k\) を並べ、各辺が次の辺と整合するようにする。具体的には、辺 \(e_i\) が終点を持ち、その終点が次の辺 \(e_{i+1}\) の始点と一致する（有向であれば向きも一致する）ことを要請する。無向グラフでは向きを気にせず、辺の端点が連結していることを確認する形になる。
辺列による記述は、辺に重みや条件が付く場合に有利である。長さが「辺の属性の集計」として定義されるとき、辺の並びそのものが自然な入力情報になるからである。
1.3 経路の長さ
1.3.1 辺数としての長さ
最も基本的な長さは、経路に含まれる辺の個数として定義される。頂点列が \(v_0, v_1, \dots, v_k\) のとき、辺数による長さは \(k\) である。単位時間や単位コストがすべての辺で同じだとみなせる状況では、辺数による最短性が意味を持つ。
辺数での最適化は探索の性質とも結びつきやすい。たとえば幅優先探索は、辺数が増える順に状態を辿るため、辺数最短の経路を効率良く見つけられることが多い。
1.3.2 重み付きグラフでの長さ
重み付きグラフでは各辺に実数（多くは非負または整数）の重みが割り当てられる。経路の長さは、経路に含まれる辺の重みの和として定義されるのが典型である。頂点列で表すなら、各隣接の辺を辿ったときの重みを順に加算する。
この枠組みでは、重みの符号や大きさの制約がアルゴリズムの選択を左右する。非負重みなら貪欲的な性質を利用しやすい一方、負の重みが含まれると、単純な最短路の確定が破綻し、負閉路の存在にも注意が必要になる。
2 経路の種類と性質
2.1 向きと経路
2.1.1 有向グラフでの経路
有向グラフでは、辺に進行方向があるため、経路は向きの整合条件を満たさなければならない。頂点列 \(v_0, v_1, \dots, v_k\) が経路となるには、各 \(v_i\) から \(v_{i+1}\) へ向く辺が存在する必要がある。したがって、無向の場合の単なる置き換えではなく、到達可能性の性質が変化する。
有向経路では、同じ2点の間でも「片方向だけ接続されている」状態が起こる。結果として、始点から終点への到達が可能でも、その逆は不可能という状況が自然に現れる。
2.1.2 無向グラフでの経路
無向グラフでは辺に方向がないため、経路の連なりは端点の一致で判定される。頂点列 \(v_0, v_1, \dots, v_k\) について、各隣接ペア \(\{v_i, v_{i+1}\}\) が辺で結ばれていれば経路とみなす。方向を区別しない分、到達可能性や連結性の指標は有向の場合より対称性を持ちやすい。
無向経路は、辺の「向き」を考えないため、探索で訪問した順序と現実の移動の対応づけが簡単になる場合がある。ただし、重みやコストを導入する際にはやはり辺属性の扱いが重要である。
2.2 単純経路と非単純経路
2.2.1 単純経路の定義
単純経路（simple path）は、頂点を重複して通らない経路である。つまり、頂点列において \(v_i = v_j\)（\(i \ne j\)）が起きないことを要求する。単純性により、経路が同じ状態へ戻る可能性が排除され、構造の解析が扱いやすくなる。
単純経路は、最短経路の探索結果が通常単純になることとも関係する。重みがすべて正であれば、同じ頂点を再訪するループは総和を増やしやすく、最適性と両立しにくいからである。
2.2.2 周路（サイクル）との関係
非単純経路では頂点の再訪が許され、場合によっては開始点と終了点が一致することがある。そのとき経路は周路（cycle）の性質を帯びる。周路とは、内部で頂点を重複しない形の閉じた経路、あるいは一般化された閉路を指す文脈で用いられるが、少なくとも「閉じる」ことが特徴になる。
単純経路と周路の関係は、再訪の有無がもたらす構造の違いにある。単純であれば閉路を含みにくく、再訪を許すと閉路が現れ得る。閉路の存在は、距離の定義や探索の枝刈りにも影響する。
2.3 閉路と開路
2.3.1 閉路の条件
閉路（閉じた経路、cycle）は、経路の始点と終点が一致することを基本条件とする。頂点列なら \(v_0 = v_k\) を満たす形で表現される。さらに厳密な「どの頂点を重複してよいか」を追加条件として課すこともあるが、まずは閉じているという性質が核になる。
閉路があると、状態の遷移が循環し得るため、到達集合の見積もりや最短化の挙動に多様性が生じる。特に重み付きでは、閉路の重みの総和が正か負かで、最適解が定まるかどうかの問題が変化する。
2.3.2 開路の扱い
開路（開いた経路）は、始点と終点が異なる経路として扱われる。頂点列では \(v_0 \ne v_k\) が条件の中心となる。開路は探索における「到達」や「移動の完了」を表しやすく、最短経路問題では、始点から任意の終点までを結ぶ開路を対象にすることが多い。
また開路は、閉路を含む場合と比べて単純な比較が可能である。目的が「到達コストの最小化」であり、終点が固定されているなら、開路の長さだけを評価して意思決定しやすい。
3 到達可能性・連結性との関係
3.1 到達可能性（リーチャビリティ）
到達可能性は、始点から終点へ経路が存在するかどうかで定義される。形式的には、ある頂点 \(s\) から頂点 \(t\) への経路が存在するとき、「\(t\) は \(s\) から到達可能」と言う。到達可能性は有向グラフでは方向に強く依存し、無向では対称性が加わるため、全体像が異なる。
到達可能性は応用面でも重要であり、遷移可能性、通信の可否、状態空間の到達範囲などを経路概念で表すことで抽象化できる。アルゴリズムでは、到達集合を計算する問題として実装されることが多い。
3.2 連結性の指標
3.2.1 有向グラフの強連結性
有向グラフで強連結性は、2つの頂点間で互いに到達可能であることを基準に定義される。すなわち、頂点 \(u\) から \(v\) へ、かつ \(v\) から \(u\) へそれぞれ経路が存在するなら、両者は強連結で結ばれているとみなす。これを全体に拡張すると、強連結成分という分解が得られ、グラフが「循環して相互到達できる塊」に整理される。
強連結性は、閉路の存在と関係しやすい。特定の成分内では戻る経路が常に確保されるため、単なる到達では捉えられない構造が見える。
3.2.2 無向グラフの連結性
無向グラフでは連結性は、任意の2頂点間に経路が存在することとして表される。これにより、グラフは連結成分へ分割できる。各成分の中では到達が可能だが、異なる成分間では到達できない。
無向の連結性は、探索によって到達集合を列挙するだけで判定できることが多い。辺の方向がないため、探索の実装がシンプルになり、分解の解釈も直感的になる。
3.3 経路と部分グラフ
3.3.1 部分グラフ上の経路
部分グラフとは、元のグラフから頂点や辺を選び出したグラフである。部分グラフ上の経路は、その部分集合に含まれる辺にのみ従って連なれる経路を指す。したがって、元グラフに存在する経路が部分グラフの制約で「途中の辺が欠ける」こともあり得る。
この点はアルゴリズムの設計と結びつく。たとえば探索を特定の領域に限定する、ある条件を満たす辺だけを使う、などの状況では、経路探索が部分グラフ上に相当し、到達集合が変化する。
3.3.2 閉包としての到達集合
到達集合は、始点から到達可能な頂点の集合として定義できるが、これを経路概念で見ると「閉包」のような振る舞いを持つ。具体的には、到達集合の定義は「経路があるなら入る」という性質に従うため、集合を経路で拡張していくと増加が止まる点が到達可能範囲の境界になる。
この閉包的な見方は、反復的な探索の正当化に役立つ。幅優先や深さ優先は、経路の延長による集合更新として理解できるため、どの頂点が含まれるべきかを体系的に導ける。
4 経路探索とアルゴリズム
4.1 最短経路の問題設定
4.1.1 目的関数（最小化）の定義
最短経路問題では、始点 \(s\) から終点 \(t\) への経路のうち、長さ（辺数または重み和）が最小となるものを求める。目的関数は「経路 \(P\) に対し \(w(P)\) を計算し、最小化する」という形で与えられる。長さの定義が異なれば最適解も変わり、同じグラフでも「最短」の意味が一致しないことがある。
また、終点が1つに固定されない場合、「始点から各頂点への最短距離」を計算する形がよく用いられる。この場合、最適性は複数の終点に対して同時に評価される。
4.1.2 到達と復元（経路復元）
最短経路は距離（またはコスト）だけでなく、実際にどの順で辺を辿るかが必要になることがある。経路復元では、探索過程で各頂点に対する前駆情報（直前に来た頂点や辺）を記録し、終点から始点へ逆に辿って経路を復元する。
復元の可否は、到達可能性と強く結びつく。始点から到達できない頂点については前駆情報が確定しないため、距離が定まらないか、特別な値として扱われる設計が一般的である。
4.2 幅優先探索（BFS）
4.2.1 辺数最短の性質
幅優先探索は、辺数が少ない順に探索を進める戦略である。無重み（あるいは各辺コストが同一）の状況では、始点からある頂点までの最短距離が辺数で定義でき、BFSはその距離最小性を保証する。これは探索の層（距離が等しい頂点集合）が段階的に拡張されるためである。
その結果、到達可能な頂点について最短経路の長さが得られ、前駆情報を用いれば経路自体も復元できることが多い。
4.2.2 距離配列と前駆情報
BFSでは通常、距離（始点からの辺数）を表す配列を保持し、未訪問を区別するための初期値を与える。頂点を初めて見つけた瞬間に最短距離が確定するため、その時点で距離と前駆情報を記録する。
前駆情報は経路復元に使われる。終点に到達した後、その前駆をたどって始点へ戻ると、探索が確定した最短の移動順を再構成できる。実装上は「訪問済み判定」と「記録のタイミング」が要点になる。
4.3 ダイクストラ法
4.3.1 非負重みの仮定
ダイクストラ法は、重み付きグラフで最短距離を求める代表的手法である。前提として辺重みが非負であることが重要で、これにより「ある距離で確定した頂点を後からより短く更新する」可能性が排除される。貪欲的に距離が最小の未確定頂点から確定していく考え方が成立する。
非負でない場合、確定済みの距離が将来の経路で下がり得るため、この手法の保証が失われる。そのため、負重みがあるときは別アルゴリズムが選択される。
4.3.2 優先度付きキューによる実装
ダイクストラ法の実装では、未確定頂点を距離の小さい順に取り出すため、優先度付きキュー（ヒープ）が用いられることが多い。距離配列を更新する際に、新しい暫定距離をキューへ投入し、取り出し時に古い情報を無視する方式が一般的である。
前駆情報も併せて更新する。ある頂点 \(v\) へのより短い経路が見つかったとき、その経路の直前にいる頂点を前駆として記録することで、後から最短経路の再構成が可能になる。
4.4 ベルマンフォード法
4.4.1 負重みの扱い
ベルマンフォード法は、辺重みに負が含まれていても動作する最短経路アルゴリズムである。反復的に全辺を「緩和」し、距離の上限を更新していく。距離が改善される限り情報が伝播し、最終的に最短距離が得られる。
この手法は、最短経路が単に存在するだけでなく、距離の定義が負に影響される状況でも正しく扱える点で重要である。計算量は増えやすいが、適用範囲の広さが利点になる。
4.4.2 負閉路の検出
ベルマンフォード法の特徴として、負閉路の検出ができる。負閉路が存在すると、そこを何度も巡ることで距離を任意に小さくでき、最短距離がそもそも下界を持たなくなる。そこで、通常の反復回数の後にさらに緩和が可能かどうかを確認する。
緩和が残っていれば負閉路が関与していると判断し、最短経路という概念が意味を失う頂点群を特定する処理が必要になる場合がある。これにより、計算結果の解釈を安全に行える。
4.5 連結性・探索目的の違い
4.5.1 到達かだけ知りたい場合
到達可能性だけが目的なら、最短性や復元を捨てて探索する戦略が合理的である。幅優先探索でも深さ優先探索でも「訪問の有無」を集めるだけで到達集合が得られる。無重みであれば最短距離まで取れるが、目的が判定のみなら記録を簡略化できる。
このように目的関数を絞ると、計算資源の使い方が最適化される。特に経路の詳細情報が不要な場面では、前駆情報を保持しない実装が選ばれることがある。
4.5.2 経路そのものが必要な場合
経路自体が必要な場合は、探索中に前駆情報を確保し、終点が決まった後に復元する設計が基本になる。最短経路を求めるなら、距離更新のタイミングに同期して前駆を更新する必要がある。さもないと、後で復元した経路が最適である保証が崩れる。
経路復元は、通信経路の提示、移動手順の提示、操作列の提示などに関わり、結果の有用性が高い。一方で、前駆情報の保存にはメモリが必要になるため、必要性とコストのバランスが設計上の論点となる。