グラフルビに隣接行列を変換する方法は？私は、ノードの最短経路を見つけたい

Question

は

Rubyでのyをノードにxは

ので、私はhttps://rosettacode.org/wiki/Dijkstra%27s_algorithm#Ruby から得たいくつかのコードを持っているが、私は仕事に私のグラフの次のフォーマットが必要になります。

どうしたらいいですか？

Answer 1

あなたの入力は配列に含まれています。これは次のように仮定しています。

arr = [[nil, 3, 10, 7, 8, nil, nil, nil, nil, nil], 
     [ 3, nil, nil, nil, 6, nil, 9, 5, nil, nil], 
     [ 10, nil, nil, 5, nil, nil, nil, nil, nil, nil], 
     [ 7, nil, nil, nil, 4, 5, nil, nil, nil, nil], 
     [ 8, 6, nil, 4, nil, 3, 4, nil, nil, 5], 
     [nil, nil, nil, 5, 3, nil, nil, nil, nil, 7], 
     [nil, 9, nil, nil, 4, nil, nil, 6, 8, 6], 
     [nil, 5, nil, nil, nil, nil, 6, nil, 11, nil], 
     [nil, nil, nil, nil, nil, nil, 8, 11, nil, 3], 
     [nil, nil, nil, nil, 5, 7, 6, nil, 3, nil]] 

あなたは、私がリンクnilと等しくに対応していない細胞を想定してきた

arr.each_with_index.with_object([]) { |(row, i), a| row.each_with_index { |v, j| 
    a << [i, j, v] unless v.nil? } } 
    #=> [[0, 1, 3], [0, 2, 10], [0, 3, 7], [0, 4, 8], [1, 0, 3], [1, 4, 6], 
    # [1, 6, 9], [1, 7, 5], [2, 0, 10], [2, 3, 5], [3, 0, 7], [3, 4, 4], 
    # ... 
    # [8, 7, 11], [8, 9, 3], [9, 4, 5], [9, 5, 7], [9, 6, 6], [9, 8, 3]] 

を書くことができます。 Float::INFINITY（この場合はa << [i, j, v] if v < Float::INFINITY）と書くことができますが、nilが便利です。

Enumerable#each_with_index,を参照してください。

• rowがarr、10要素の配列の要素である：以下のように|(row, i), a|のブロック変数です。
• iは、行インデックス（-9）です。
• aは、最初に空の配列（each_with_object([])）で、ブロックによってビルドされて返されます。