マップを保存する方法RubyでBFSを含むグラフを生成する方法

Question

だから、これはCSのMSCを持つ誰かにとって古典的な質問だと思います。

私にはn要素があり、距離もあります。次の距離を持つ3つの要素があるとしましょう。対称です

A -> B == B -> A

マトリックスのように見えます：

   A,  B,  C,  
A  0, 10,  20 
B 10,  0,  30
C 20, 30,   0

私の質問は次のとおりです。

• これを効率的に保存するにはどうすればよいですか（どのデータ構造）
• 距離の合計が最小限のリンクリストを取得する最も効率的な方法は何ですか

この場合、最高はです

B -> A -> C = 30 which equals to C -> A -> B

その他のケース：

A -> B -> C = 40 which equals to C -> B -> A

私はBFSがこれに適しているかもしれないという印象を持っていました。英語のドキュメントへのリンクは良いです、Amazonの本でさえ...

Answer 1

データ構造に理想的なソリューションは次のとおりです 隣接リスト.

隣接リストは、単にオブジェクトのリストです（グラフの頂点を表します）。各オブジェクトには、隣接するエッジと対応する重量があるすべての頂点を含むリストがあります。

Rubyでは、簡単な実装が次のように見えるかもしれません。

vertices = {}
a = Vertex.new
b = Vertex.new

a.add(b, 10)
b.add(a, 10)

vertices[a] = a
vertices[b] = b

最短の加重パスを見つけるためのアルゴリズムは呼び出されます ディクストラ.

アルゴリズムを実行した後に最短のパスを取得したい場合は、トレースバックを行うことができます。これは、各ノードの（最適な）親を到達するときに保存することによって行われます。これを行うには、訪問したノードごとにハッシュを使用すると、ノードにマップしてコストが最小のノードにマップされます。

アルゴリズムを完了すると、再帰的なトレースバックは次のようになる可能性があります。

def traceback(parent, start, node, path)
  if(start == node)
     (path + start.to_s).reverse
  else
     path += node.to_s + " "
     traceback(parent, start, parent[node], path)
  end
end

Answer 2

聞こえます ディクストラ 加重グラフをナビゲートするアルゴリズムがあります。