はじめに

前回の記事で配列より高速に動作するpriority queueを作りました
使用例としてdijkstra法の中に実装してみました
今回は行先とコストをデータとして持つエッジクラスのコストが最小の順で取り出したいので比較式をオーバーロードしなければなりません
ですが比較式は全て(<,<=,>,>=,==,!=など)を定義する必要は無く
<=>だけをオーバーロードすればそのすべてに適用されるみたいです
返り値が負だと「<」,同じだと「==」,正だと「>」に該当します

実装

dijkstra.rb

require './heap'

class Edge
  include Comparable
  attr :to, :cost
  def initialize e
    @to = e[0]
    @cost = e[1]
  end
  def <=>(other)
    return @cost - other.cost
  end
end

pq = HeapArray.new
node=[]
dist=[]

# initialize
n=gets.to_i
n.times do |i| 
  node[i]=[]
  dist<<nil
end
s,g =gets.split(" ").map{|num| num.to_i}

while e=gets 
  e=e.gsub("->"," ").split(" ").map{|num| num.to_i}
  node[e[0]] << Edge.new([e[1],e[2]])
end


dist[s]=0
pq.push Edge.new([0,s])

# dijkstra main loop
while !pq.empty?
  v = pq.pop
  unless dist[v.to].nil?
    next if dist[v.to] < v.cost
  end

  node[v.to].each do |e|
    unless dist[e.to].nil?
      next if dist[e.to] < dist[v.to] + e.cost
    end
#    puts "#{e.to}:#{dist[e.to]} <= #{dist[v.to] + e.cost} = #{dist[v.to]} + #{e.cost} (#{v.to}->#{e.to})"
    dist[e.to] = dist[v.to] + e.cost
    pq.push Edge.new([e.to,dist[e.to]])
  end
#  print "Best Distance (Temporary) : #{dist}\n"
end

puts "The distance using best way of #{s} -> #{g} is ... #{dist[g]}"

=begin
# input example
## first row is a number of node
## second row is a start and end node separated by a space
## and the rest is edge information (<sorce>-><dist> <cost>)
6
0 4
0->1 5
0->2 4
0->3 2
1->0 5
1->2 2
1->4 6
2->0 4
2->1 2
2->3 3
2->5 2
3->0 2
3->2 3
3->5 6
4->1 6
4->5 4
5->2 2
5->3 6
5->4 4
=end

作業ディレクトリに前回の"heap.rb"を入れて動かしてみてください
empty?メソッドも必要なのでそれも追加してください

heap.rb

  def empty?
    return @heapArr.empty?
  end

一応効率が悪いですがpqを配列に書き換えても動きます

HeapArrayクラスが比較演算子を持つにもかかわらずちゃんと動いていることがわかりました