ALGORITHM NOTE グラフ 最短経路
All Pairs Shortest Path (APSP) problem (全対最短経路問題) は、グラフ G(V, E) に対して、G に含まれるノードの全てのペアの最短経路（距離）を求める問題です。G に負の重みのあるエッジがなければ、この問題は各ノードを起点として Dijkstra's Algorithm を |V| 回行うことによって解くことができます。この方法のオーダーは O(|V|3) または O(|V|(|E| + |V|)log|V|) となります。 Floyd's algorithm は APSP 問題を O(|V|3) で解くことができます。しかも Floyd's algorithm は、G に負の閉路がない限り、G に負の重みを持つエッジが存在しても正しく動作します。負の閉路とは、その閉路を成すエッジの重みの合計が負となっている閉路です（負の閉路をもつとき G に
ALGORITHM NOTE 隣接行列
行列という名の通り、グラフを２次元配列で表現します。配列のインデックスが各ノードの番号に対応します。例えば、この２次元配列を M とすると、M[i][j] がノード i とノード j の関係を表します。 無向グラフ ノード i とノード j の間にエッジがある場合、M[i][j] と M[j][i] の値を 1 とします。エッジがない場合は 0 とします。隣接行列は右上と左下が対照になります。 有向グラフ ノード i からノード j へ向かってエッジがある場合、M[i][j] の値を 1 とします。エッジがない場合は 0 とします。 重みつき無向グラフ ノード i とノード j の間に重さ w のエッジがある場合、M[i][j] と M[j][i] の値を w とします。エッジがない場合は、問題上有り得ない値に設定します。例では∞としていますが、プログラムでは非常に大きな値に設定しておくと
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
