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