0
Help us understand the problem. What are the problem?

More than 5 years have passed since last update.

posted at

# はじめに

ですが比較式は全て(<,<=,>,>=,==,!=など)を定義する必要は無く
<=>だけをオーバーロードすればそのすべてに適用されるみたいです

# 実装

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
``````

empty?メソッドも必要なのでそれも追加してください

heap.rb
``````  def empty?
return @heapArr.empty?
end
``````

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

Register as a new user and use Qiita more conveniently

1. You get articles that match your needs
2. You can efficiently read back useful information
What you can do with signing up
0
Help us understand the problem. What are the problem?