def moore_dijkstra( dep, arv )
dep = @graph.get_node(dep) unless dep.kind_of?(GraphViz::Node)
arv = @graph.get_node(arv) unless arv.kind_of?(GraphViz::Node)
m = distance_matrix
n = @graph.node_count
c = [dep.index]
d = []
d[dep.index] = 0
pred = []
@graph.each_node do |name, k|
if k != dep
d[k.index] = m[dep.index+1,k.index+1]
pred[k.index] = dep
end
end
while c.size < n
mini = 1.0/0.0
y = nil
@graph.each_node do |name, k|
next if c.include?(k.index)
if d[k.index] < mini
mini = d[k.index]
y = k
end
end
break unless mini.to_f.infinite?.nil?
c << y.index
@graph.each_node do |name, k|
next if c.include?(k.index)
if d[k.index] > d[y.index] + m[y.index+1,k.index+1]
d[k.index] = d[y.index] + m[y.index+1,k.index+1]
pred[k.index] = y
end
end
end
ch = []
k = arv
while k.index != dep.index
ch.unshift(k.id)
k = pred[k.index]
end
ch.unshift(dep.id)
if d[arv.index].to_f.infinite?
return nil
else
return( {
:path => ch,
:distance => d[arv.index]
} )
end
end