ダイクストラ法

重み付きグラフにおいて、始点から全ての頂点への最短経路を求めるアルゴリズム。辺の重みが非負の場合に使用でき、貪欲法に基づく。計算量はO(V²)だが、優先度付きキューを使うとO((V+E)log V)に改善できる。

辺の重みが負でないグラフで、出発点から各頂点への最短経路を求めるアルゴリズム。最短距離が確定していない頂点のうち、出発点からの距離が最小のものを確定させ、そこから出る辺で隣の頂点の距離を更新することを繰り返す。優先度付きキューを使うとO((V＋E) log V)で計算できるが、負の重みの辺があると正しく求められない。

辺の重みが負でない重み付きグラフで、出発点から各頂点への最短経路を求めるアルゴリズム。最短距離が確定していない頂点のうち距離が最小のものを確定させ、そこから隣接する頂点の距離を更新することを繰り返す。OSPFの経路計算に使われている。

グラフや木構造を探索する際、可能な限り深い方向に進み、行き止まりになったら戻って別の枝を探索するアルゴリズム。スタック（再帰呼出し）を用いて実装される。迷路探索やトポロジカルソートに利用。

グラフや木構造を探索する際、始点から近い順に全隣接ノードを探索してから次の階層に進むアルゴリズム。キューを用いて実装される。重みなしグラフの最短経路探索に適しており、Web巡回やSNSの友達推薦に応用。

グラフ上の2点間で、辺の重みの合計が最小になる経路を求める処理。カーナビの経路案内やネットワークのルーティングに使われる。代表的な解法にダイクストラ法やベルマンフォード法がある。

最短経路を求めるアルゴリズムの一つ。すべての辺について距離の更新を繰り返す。ダイクストラ法より遅いが、重みが負の辺を含むグラフでも扱え、負の閉路があることも検出できる。

頂点（ノード）と辺（エッジ）からなるグラフ構造を扱う数学分野。無向グラフ、有向グラフ、重みつきグラフ、完全グラフなどの種類があり、ネットワーク設計、最短経路問題、スケジューリングなどに応用される。

最適化問題を部分問題に分割し、各部分問題の最適解を記憶して再利用することで全体の最適解を効率的に求める手法。ナップサック問題や最短経路問題などに適用され、メモ化再帰やボトムアップ方式で実装される。