如何將鄰接矩陣轉化爲圖形ruby？

Question

我想找到節點的最短路徑X到節點Y在Ruby中

所以我有一些代碼，我從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,Enumerator#with_object。在|(row, i), a|塊變量如下：

• row是arr，一個10元件陣列的元件。
• i是行索引（0-9）。
• a是一個最初爲空的數組（each_with_object([])），它將由該塊生成並返回。