Skip to content

Instantly share code, notes, and snippets.

@yevhene
Last active December 23, 2015 18:19
  • Star 0 You must be signed in to star a gist
  • Fork 1 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save yevhene/6674560 to your computer and use it in GitHub Desktop.
class Edge
attr_accessor :src, :dest, :length
def initialize(src, dest, length = 1)
@src = src
@dest = dest
@length = length
end
end
class Graph < Array
attr_reader :edges
def initialize
@edges = []
end
def connect(src, dest, length = 1)
@edges.push Edge.new(src, dest, length)
end
def neighbors(vertex)
neighbors = []
@edges.each do |edge|
neighbors.push edge.dest if edge.src == vertex
end
return neighbors.uniq
end
def length_between(src, dest)
@edges.each do |edge|
return edge.length if edge.src == src and edge.dest == dest
end
nil
end
end
class Dijkstra
def initialize(graph, src, dest)
@graph = graph
@src = src
@dest = dest
reset
end
def reset
@dist = {}
@prev = {}
@graph.each { |vertex| @dist[vertex] = @prev[vertex] = nil }
@dist[@src] = 0
@vertices = @graph.clone
end
def find_nearest_vertex
@nearest_vertex = @vertices.inject do |a, b|
next b unless @dist[a]
next a if !@dist[b] || @dist[a] < @dist[b]
b
end
end
def update_weights(vertex)
alt = @dist[@nearest_vertex] + @vertices.length_between(@nearest_vertex, vertex)
if @dist[vertex].nil? or alt < @dist[vertex]
@dist[vertex] = alt
@prev[@vertices] = @nearest_vertex
end
end
def run_through_neighbours
@vertices.neighbors(@nearest_vertex).each do |vertex|
update_weights(vertex)
end
@vertices.delete @nearest_vertex
end
def run
until @vertices.empty?
return @dist[@dest] if @dest and find_nearest_vertex == @dest
run_through_neighbours
end
@dest ? nil : @dist
end
end
graph = Graph.new
(1..5).each {|node| graph.push node }
graph.connect 1, 2, 10
graph.connect 1, 3, 5
graph.connect 2, 3, 2
graph.connect 2, 4, 1
graph.connect 3, 2, 3
graph.connect 3, 4, 9
graph.connect 3, 5, 2
graph.connect 4, 5, 4
graph.connect 5, 4, 6
graph.connect 5, 1, 7
p Dijkstra.new(graph, 1, 4).run
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment