ワーシャル・フロイド法での全点対最短経路を求めるアルゴリズム
任意の2頂点間の最短距離を求める問題を全点対最短経路問題といいます。
ワーシャル・フロイド法は、動的計画法を用いて全点対最短経路を求める有名なアルゴリズムです。
負の辺が含まれていても動作する負の閉路がある場 ...
木の直径を求めるアルゴリズム
木に存在する2つノード間の最大距離を木の直径と言います。
重み無しの木でも、重み付きの木でも、木の最遠頂点間の距離が直径になります。
重み無しの木の例:
以下は直径が5となる木の例で
ダイクストラ法による単一始点最短経路を求めるアルゴリズム
グラフにおける単一始点最短経路問題とは、始点を固定した時に、他のすべての頂点への最短経路を求める問題のことです。
ダイクストラ法は、単一始点最短経路問題を解く時に利用され、利点としては
計算量が \(O(|E| \l ...ベルマンフォード法による単一始点最短経路を求めるアルゴリズム
グラフにおける単一始点最短経路問題とは、始点を固定した時に、他のすべての頂点への最短経路を求める問題のことです。
ベルマンフォード法は、単一始点最短経路問題を解く時に利用され、
負の辺が含まれているような場合でも適用 ...グラフ(Graph)のデータ構造と基本用語の定義
グラフとは
頂点同士がつながっているか(隣接しているか)を表す、辺(エッジ)の集合 ...
頂点(ノード)と、頂点同士の関係を表したデータ構造です。
数学的には、グラフは以下の2つから構成されます。
頂点(ノード)の集合頂点同士がつながっているか(隣接しているか)を表す、辺(エッジ)の集合 ...