DijkstrasShortestPath.rb

DijkstrasShortestPath.rb

require 'matrix'
=begin 
:mat utter, 10/19/2014
=end
class Graph
	From   = 0
	To     = 1
	Length = 2
	def initialize()
		@graph = Array.new
		@table = Array.new
		@visit = Hash.new
		@index = Hash.new
	end
	def add(key,val,dist)
		@visit[key] = false
		@visit[val] = false
		@index[key] = @index.size if !@index.has_key?(key)
		@index[val] = @index.size if !@index.has_key?(val)
		@graph.push( [key, val, dist] )
	end
	def to_s
		return "#{@graph}\n#{@visit}"
	end
	def G
		@graph
	end
	def finalize( start )
		_empty
		

		g = @graph
		t = @table
		v = @visit
		i = @index


		vect = Array.new
		
		for y in 0..t.size - 1 do
			#branch = self.branch( g, i.keys[y] )
			#print branch, "\n"
			temp = nil
			self.branch( g, i.keys[y] ).each do | vertex |
				next if v[vertex[From]]
				temp = vertex[From]

				t[y][ i[vertex[To]] ] = [vertex[Length],vertex[From]]

			end
			v[temp] = true
			#for x in 0..t.size - 1 - y do	
			#end
		end
		self.table
	end

	def branch( g, a )
		b = Array.new
		g.each do | v |
			b.push( v ) if v[From] == a
		end
		b.sort_by!{ | v | v[Length] }
	end

	def table
		size = @index.size - 1

		@index.each_key { | i | print "\t#{i}" }
		puts
		for y in 0..size
			print "#{@index.keys[y]}\t"
			for x in 0..size
				print "#{@table[y][x]}\t"
			end
			puts
		end
	end

private
	def _empty
		print "vertices:\t#{@visit.size}\n"
		print "edges   :\t#{@graph.size}\n"
		@table = Array.new(@visit.size) { |i| @table[i] = Array.new }
		size = @index.size - 1
		for y in 0..size
			for x in 0..size
				@table[y][x] = nil
			end
		end
	end

end

g = Graph.new
g.add(:A,:B, 1)
g.add(:A,:E, 3)
g.add(:B,:C, 4)
g.add(:C,:F, 1)
g.add(:C,:D, 6)
g.add(:E,:D, 1)
g.add(:D,:B, 4)
g.add(:D,:E, 3)
g.finalize( :A ) #pass in starting vert

shortestDistPath.rb

require 'matrix'
=begin 
:mat utter, 10/19/2014
=end
class Graph
	Inf = +1.0/0.0
	Dist = 2
	From = 0
	To   = 1
	Vertex = Struct.new( :dist, :prev )
	def initialize()
		@graph = Hash.new
		@data  = Array.new
		@children = Hash.new
	end
	def to_s
		return "#{@graph}\n"
	end
	def add(key,val,dist)
		v = [key,val,dist]
		@data.push( v )
		@children[ key ] = Array.new if !@children.has_key?( key )
		@children[ key ] << v
		@graph[ key ] = Vertex.new(Inf, false)
		@graph[ val ] = Vertex.new(Inf, false)
	end

	def searchAll( goal )
		@graph.each_key do | x |
			path = []
			u = x
			while u 
				path.unshift( u )
				u = @graph[ u ].prev
				break if u == goal
			end
			print path, "\n"
		end	
	end

	def search( start, finish )
		d = dup( @data )
		@graph[start].dist = 0

		until d.empty?
			v = d.min_by { |v| v[Dist] }
			d.delete( v )

			@children[ v[From] ].each do | from, to, dist |
					new_dist = v[Dist] + dist
					#print "--> #{from},#{to},#{dist} \t\t #{v[Dist]} -> #{new_dist}\n"
					if new_dist < @graph[ to ].dist
						@graph[ to ].dist = new_dist
						@graph[ to ].prev = from
					end
			end

		end
=begin
		@graph.each do |x|
			print "\n#{ x }"
		end
=end
	end
	def dup(a)
		return Marshal.load( Marshal.dump(a) )
	end
end

g = Graph.new()
g.add(:a,:b, 4)
g.add(:a,:c, 2)
g.add(:b,:d, 2)
g.add(:b,:e, 3)
g.add(:b,:c, 3)
g.add(:c,:e, 5)
g.add(:c,:d, 4)
g.add(:c,:b, 1)
g.add(:e,:d, 1)

g.search( :d, :e) 
g.searchAll( :d )
puts