Bellman-Ford algorithm

gistfile1.rb

class Vertice
  attr_accessor :predecessor, :d, :name
  def initialize(n)
    @name = n
  end
end

class Edge
  attr_accessor :source, :destination, :w
  def initialize(s,d,w)
    @source = s
    @destination = d
    @w = w
  end
  
end


def relax(edge)
  if edge.destination.d > edge.source.d + edge.w
    edge.destination.d = edge.source.d + edge.w
    edge.destination.predecessor = edge.source
  end
end

def initialize_single_source(vertices, s)
  vertices.each do |v|
    v.d = Float::INFINITY
    v.predecessor = nil
  end
  s.d = 0
end

def bellman_ford(vertices, edges, s)
  initialize_single_source(vertices, s)
  for i in 1..vertices.size
    edges.each do |e| 
      relax(e)
    end
  end
  edges.each do |e|
    return false if e.destination.d > e.source.d + e.w 
  end
end

vertices = []
edges = []

s = Vertice.new('s')
vertices << s
t = Vertice.new('t')
vertices << t
x = Vertice.new('x')
vertices << x
y = Vertice.new('y')
vertices << y
z = Vertice.new('z')
vertices << z

edges << Edge.new(t,x,5)
edges << Edge.new(t,y,8)
edges << Edge.new(t,z,-4)
edges << Edge.new(x,t,-2)
edges << Edge.new(y,x,-3)
edges << Edge.new(y,z,9)
edges << Edge.new(z,x,4)
edges << Edge.new(z,s,2)
edges << Edge.new(s,t,6)
edges << Edge.new(s,y,7)

bellman_ford(vertices, edges, s)

vertices.each {|v| puts "#{v.name} #{v.d} #{v.predecessor.name if !v.predecessor.nil?}"}