1

まず、構造が正しいことを確認したいと思います。私の知る限り、グラフを表す隣接リストは次のようになります。

隣接リスト

AdjList は、各要素がオブジェクトである ArrayList です。各オブジェクトには、接続された頂点を表す ArrayList が内部に含まれています。たとえば、上の画像では、頂点 1 (AdjList の最初のインデックス) が AdjList のインデックス 2、4、および 5 の頂点に接続されています。隣接リストのこの表現は正しいですか? (ps: インデックスが 0 から始まることはわかっています。簡単にするためにここに 1 を入れます)。

正しい場合、2 つの頂点間の最短経路を見つけるにはどのアルゴリズムを使用すればよいですか?

4

4 に答える 4

4

2 つの頂点間の最短パスだけを提供するアルゴリズムはありません。次のいずれかを使用できます。

  1. ダイクストラのアルゴリズムを使用して、1 つの頂点と他のすべての頂点の間の最短パスを見つけます (そして、必要なものを選択します)。
  2. Roy-Floyd アルゴリズムを使用して、考えられる頂点のすべてのペア間の最短経路を見つけます。

リンクには疑似コードも含まれています。

于 2011-12-17T19:52:13.527 に答える
2

ダイクストラのJava での最短パス アルゴリズムの例と説明を次に示します。

于 2011-12-17T19:52:01.007 に答える
1

Dijkstra と Floyd Warshall を使用できます。重み付けされていないグラフの場合、各エッジの重みを 1 と仮定し、アルゴリズムを適用します。

于 2012-07-11T08:12:39.120 に答える