secret
Created — forked from valeriofarias/short-circuit.rb

  • Download Gist
short-circuit.rb
Ruby
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97
# Ruby Programming Challenge For Newbies
# RPCFN: Short Circuit (#3)
# By Gautam Rege
# Solution by Valério Farias
#
# To find the smallest path I used the dijkstra algorithm.
# My inspiration was this example: http://snippets.dzone.com/posts/show/7331
# To execute the class first load the file:
# require 'short-circuit'
# Then initialize the class:
# gr = Graph.new([['a','b',50],['a','d',150],['b','c',250],['b','e',250],['c','e',350],['c','d',50],['c','f',100],['d','f',400],['e','g',200],['f','g',100]])
# Finally use the method solve putting the source and the target values in the parameters:
# gr.solve('a','g')
# This must return the solution:
# => [["a", "b", 50], ["b", "c", 250], ["b", "e", 250], ["c", "e", 350], ["d", "f", 400], ["e", "g", 200]]
 
class Graph
 
attr_reader :list, :solution
 
def initialize(graph)
@graph = {}
@nodes = Array.new
@INFINITY = 1 << 32
@list = graph
 
graph.each do |item|
source = item[0]
target = item[1]
weight = item[2]
 
if @graph.has_key?(source)
@graph[source][target] = weight
else
@graph[source] = {target => weight}
end
 
if @graph.has_key?(target)
@graph[target][source] = weight
else
@graph[target] = {source => weight}
end
 
@nodes << source unless @nodes.include?(source)
@nodes << target unless @nodes.include?(target)
end
end
 
# based of wikipedia's pseudocode: http://en.wikipedia.org/wiki/Dijkstra's_algorithm
def dijkstra(s)
@distance = {}
@prev = {}
 
@nodes.each do |i|
@distance[i] = @INFINITY
@prev[i] = -1
end
 
@distance[s] = 0
node_list = @nodes.compact
while (not node_list.empty?)
smallest = nil;
node_list.each do |min|
if (not smallest) or (@distance[min] and @distance[min] < @distance[smallest])
smallest = min
end
end
 
break if @distance[smallest] == @INFINITY
 
node_list = node_list - [smallest]
@graph[smallest].keys.each do |v|
alt = @distance[smallest] + @graph[smallest][v]
if (alt < @distance[v])
@distance[v] = alt
@prev[v] = smallest
end
end
end
end
 
def solve(s,t)
smallest_path = []
@solution = @list
dijkstra(s)
 
while(@prev[t]!= -1)
smallest_path << [@prev[t], t, @graph[t][@prev[t]]]
smallest_path << [t, @prev[t], @graph[t][@prev[t]]]
t = @prev[t]
end
 
# solution == list - smallest_path
smallest_path.each{ |i| @solution = @solution - [i] }
return @solution
end
end

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.