그래프 루비에 인접 매트릭스를 변환하는 방법은 무엇입니까? 내가 노드의 최단 경로를 찾으려면

Question

는

루비에서 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, Enumerator#with_object을 참조하십시오.

• row는 arr, 10 배열 요소의 원소이다 : 다음의 블록 |(row, i), a| 변수이다.
• i은 행 색인 (0 - 9)입니다.
• a은 블록에 의해 빌드되고 반환 될 초기 비어있는 배열 (each_with_object([]))입니다.