[Ruby][Algorithm][Newbie] Попытка реализации алгорима Прима на Ruby.

Строки 104 и 115 не будут работать так, как тебе хотелось бы. Ты итерируешь по масиву, который внутри блока модифицируешь (удаляешь элементы).

А где же тогда удалять?

Вообще интересует, правильно ли спланировано приложение, или есть замечания? Нет никого рядом сейчас, кто мог бы проверить, вот и обращаюсь.

> А где же тогда удалять?

Посмотри что твой код делает со 104 до 118 строки. :-) Как ты себе представляешь итерирование по элементам массива, из которого ты удаляешь элементы, то есть вот такое:

a = [1, 2, 3]
a.each {|i| a.delete i }

С чего начинал программирование на Руби?

С рельсов и «Programming Ruby: The Pragmatic Programmer's Guide».

Если удалять вершину вне итерации, а в теле while pQ != [], что логичнее, то цикл становится бесконечным. А так он все правильно делает, кажется.

> «Programming Ruby: The Pragmatic Programmer's Guide». 

В этой книге есть вообще всё, что нужно знать о Руби. Почитай её внимательнее.

> Если удалять вершину вне итерации, а в теле while pQ != [], что логичнее, то цикл становится бесконечным. А так он все правильно делает, кажется.

Массивы имеют метод empty?, то есть вместо "pQ != []" намного приятнее видеть while not pQ.empty? do. Ты посмотри где твой closest_point находится и появляется... подумай над вот этим:

[1, 2].each {|i|
 a = 1
}
puts a

Это есть в твоей программе. Когда подумаешь, поймешь почему цикл в бесконечный превращается. :-)

Вообще, на Руби в таком стиле как ты обычно не пишут. 

Как пример, я тебе написал свой вариант реализации алгоритма Прима (чисто иллюстративный, но рабочий :-):

def prim(a)
  tree = [(a.delete(a.min {|x, y| x[2] <=> y[2]}))] 
  loop {
    tree_vert = tree.collect {|x| x[0,2]}.flatten.uniq
    adges = a.select {|x| (tree_vert & x[0,2]).size == 1 }
    break if adges.empty?
    tree << (a.delete(adges.min {|x, y| x[2] <=> y[2]}))
  }
  tree
end

Метод принимает массив (не пустой), описывающий граф и возвращает остовное дерево минимального стоимости. Массив должен состоять из массивов по 3 элемента [вершина, вершина, вес]. Например [[1, 2, 3.254], [1, 3, 1.2], [2, 3, 5.01]]. Возвращаемый массив такой же.

Спасибо за подсказки, решил.

# Пока не пуст массив неприсоединенных вершин    
while not pQ.empty?
    
    # Принимаем минимальную дистанцию за (псевдо)бесконечность 
    min_dist = 10**10
        
	# Для каждой неприсоединенной вершины
    for point in pQ
        
        # Если расстояние от неё до дерева меньше, чем минимальная дистанция
        if point.distance < min_dist
            
            # Устанавливаем минимальную дистанцию, взятую из текущей вершины
            min_dist = point.distance
                
            # Запоминаем точку, как ближайшую    
            closest_point = point		
        end
    end
    pQ.delete(closest_point)
    p0 = closest_point				
    p1 = closest_point.predecessor
        
    # Создаем линию, соединяющую ближайшие вершину	
    lines.push(Line.new(p0, p1))		
    # Для оставшихся вершин
    pQ.each do |point|
        
        # Вычисляем дистанцию 					
        d = dist(point, closest_point)
            
        # Если меньше, чем вычисленная ранее
        if d < point.distance
            # Устанавливаем новую, меньшую				
            point.distance = d			
            # Устанавливаем в качестве предшественника ближайшую точку
            point.predecessor = closest_point 
        end
    end
end

А по поводу стиля написания, да, развращающее влияние PHP и отсутствие практики. Еще раз спасибо.