class Ogr::ShortestPaths
Finds shortest paths in graph using Dijkstra algorithm
Attributes
distance[R]
graph[R]
parent[R]
queue[R]
Public Class Methods
new(graph, source)
click to toggle source
# File lib/ogr/shortest_pahts.rb, line 7 def initialize(graph, source) @graph = graph @queue = IndexedPriorityQueue.min @parent = {} @distance = {} @graph.vertexes.each { |v| @distance[v] = Float::INFINITY } find_paths(source) end
Public Instance Methods
distance_to(goal)
click to toggle source
# File lib/ogr/shortest_pahts.rb, line 17 def distance_to(goal) distance[goal] end
find_paths(source)
click to toggle source
# File lib/ogr/shortest_pahts.rb, line 36 def find_paths(source) distance[source] = 0 queue.push(source, 0) while v = queue.shift graph.neighbors(v).each do |u| relax(graph.get_edge(v, u)) end end end
found_better(edge, new_distance)
click to toggle source
# File lib/ogr/shortest_pahts.rb, line 52 def found_better(edge, new_distance) v = edge.to distance[v] = new_distance parent[v] = edge.from if queue.include?(v) queue.update(v, new_distance) else queue.push(v, new_distance) end end
from(goal)
click to toggle source
# File lib/ogr/shortest_pahts.rb, line 21 def from(goal) parent[goal] end
path?(goal)
click to toggle source
# File lib/ogr/shortest_pahts.rb, line 25 def path?(goal) distance[goal] < Float::INFINITY end
path_to(goal)
click to toggle source
# File lib/ogr/shortest_pahts.rb, line 29 def path_to(goal) v = goal path = [v] path.push v while v = parent[v] path.reverse end
relax(edge)
click to toggle source
# File lib/ogr/shortest_pahts.rb, line 47 def relax(edge) new_distance = distance[edge.from] + edge.weight found_better(edge, new_distance) if new_distance < distance[edge.to] end