ベルマン・フォード法

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

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

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

グラフのすべての頂点の組の間の最短経路を一度に求める動的計画法のアルゴリズム。頂点kを経由した方が近くなるなら距離を更新するという処理を、すべての頂点kについて順に行う。計算量はO(V³)で、負の重みの辺があっても負の閉路がなければ求められ、実装が簡単で、頂点数が少ないグラフに向く。

中心から放射状に伸ばした複数の軸に各項目の値をとり、点を線で結んだ多角形で表すグラフ。複数の評価項目のバランスを一目で把握でき、製品や人材の評価、他社との比較などに使う。各軸の目盛りの範囲をそろえないと、形から受ける印象が実際の差と食い違う。

重み付きの連結な無向グラフで、すべての頂点を閉路なしにつなぐ木（全域木）のうち、辺の重みの合計が最小になるもの。拠点を結ぶ通信網や配線、道路を最も安い費用で敷設する問題などに使われる。重みの小さい辺から選ぶクラスカル法と、木を1頂点ずつ広げるプリム法で求める。

各辺に流せる量の上限（容量）が決まったネットワークで、出発点（ソース）から終点（シンク）まで流せるフローの総量の最大値を求める問題。まだ流せる経路（増加道）を見つけて流量を増やすことを繰り返すフォード・ファルカーソン法などで解く。最大フローは、ネットワークを2つに分ける辺の容量の合計の最小値（最小カット）に等しい（最大フロー最小カット定理）。

2つの変数の関係を点の分布で表すグラフ。横軸と縦軸にそれぞれ変数をとり、データを点として打つことで相関関係を視覚的に把握できる。QC7つ道具の一つ。