ダイクストラ法

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

重み付きグラフにおける単一始点最短経路を求めるアルゴリズム。始点から各頂点への暫定最短距離を管理し、最小の頂点を確定させながら隣接頂点の距離を更新する。負の重みには対応できない。優先度付きキューで効率化可能。

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

パケットを宛先のネットワークまで届けるために、ルータが経路表（ルーティングテーブル）を基に次の転送先を決めること。管理者が経路を手動で設定する静的ルーティングと、RIP、OSPF、BGPなどのルーティングプロトコルで経路情報を交換して自動的に更新する動的ルーティングがある。

頂点（ノード）と、頂点どうしを結ぶ辺（エッジ）からなるグラフの性質を研究する数学の分野。向きのある有向グラフ、向きのない無向グラフ、辺に重みを持つ重み付きグラフがあり、最短経路や最小全域木、ネットワークの経路制御、SNSの関係の分析などに応用される。

重み付きグラフで、出発点から各頂点への最短経路を求めるアルゴリズム。すべての辺について距離の更新を頂点数−1回繰り返すことで、負の重みの辺があっても最短経路を求められ、負の閉路の存在も検出できる。ダイクストラ法より計算量は大きい。

最小全域木を求めるアルゴリズムの一つ。すべての辺を重みの小さい順に並べ、閉路ができない場合に限ってその辺を採用することを、頂点数－1本の辺を選ぶまで繰り返す。閉路の判定には、頂点が同じ集合に属するかを素早く調べるUnion-Find（素集合データ構造）を使い、計算量は辺の整列が支配的でO(E log E)である。

最小全域木を求めるアルゴリズムの一つ。任意の1頂点から始め、作りかけの木に含まれる頂点と含まれない頂点を結ぶ辺のうち重みが最小のものを選んで木を広げることを、すべての頂点が含まれるまで繰り返す。優先度付きキューを使うとO(E log V)で計算でき、辺の多い密なグラフに向く。