Skip to content

Instantly share code, notes, and snippets.

@manoamaro
Created June 26, 2012 23:36
Show Gist options
  • Save manoamaro/3000167 to your computer and use it in GitHub Desktop.
Save manoamaro/3000167 to your computer and use it in GitHub Desktop.
Bellman-Ford algorithm
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?}"}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment