class Dijkstra
Public Class Methods
new(startpoint, endpoint, matrix_of_road)
click to toggle source
constructor of the class
# File lib/dijkstra.rb, line 4 def initialize(startpoint, endpoint, matrix_of_road) #start node @start = startpoint #end node @end = endpoint @path = [] @PInfinit = 88 readAndInit( matrix_of_road ) #Dijkstra's algorithm in action and good luck dijkstra() end
Public Instance Methods
ROAD(node)
click to toggle source
# File lib/dijkstra.rb, line 34 def ROAD(node) if @F[node] != 0 ROAD(@F[node]) end @path.push(node) end
dijkstra()
click to toggle source
# File lib/dijkstra.rb, line 42 def dijkstra() start = @start min = @PInfinit posMin = @PInfinit (1..@nodes-1).each do |i| @R[i] = @road[start][i] if i != start if @R[i] < @PInfinit @F[i] = start end end end #for debug #print @R @S[start] = 1 #for debug #print @S (1..@nodes-2).each do |d| min = @PInfinit (1..@nodes-1).each do |i| if @S[i] == 0 if @R[i] < min min = @R[i] posMin = i end end end @S[posMin] = 1 (1..@nodes-1).each do|j| if @S[j] == 0 if @R[j] > @R[posMin] + @road[posMin][j] @R[j] = @R[posMin] + @road[posMin][j] @F[j] = posMin end end end end end
getCost()
click to toggle source
This method determines the minimum cost of the shortest path
# File lib/dijkstra.rb, line 24 def getCost() @R[@end] end
getShortestPath()
click to toggle source
get the shortest path
# File lib/dijkstra.rb, line 29 def getShortestPath() ROAD(@end) @path end
readAndInit( arr )
click to toggle source
# File lib/dijkstra.rb, line 93 def readAndInit( arr ) @nodes = arr[0][0]+1 n = arr.size()-1 @road = Array.new(@nodes) { Array.new(@nodes) } @R = Array.new(@nodes) @S = Array.new(@nodes) @F = Array.new(@nodes) (0..@nodes-1).each do |i| @R[i] = 0 end (0..@nodes-1).each do |i| @S[i] = 0 end (0..@nodes-1).each do |i| @F[i] = 0 end (0..@nodes-1).each do |i| (0..@nodes-1).each do |j| if i == j @road[i][j] = 0 else @road[i][j] = @PInfinit end end end (1..n).each do |i| x = arr[i][0] y = arr[i][1] c = arr[i][2] @road[x][y] = c end end
writeToFile(filename)
click to toggle source
# File lib/dijkstra.rb, line 134 def writeToFile(filename) f = File.open(filename,"w") out = "Cost -> " + @R[@end].to_s + "\nShortest Path -> " + @path.to_s f.write(out) f.close() end