class Dijkstra

Public Class Methods

new(graph, source) click to toggle source

source node and graph needed

# File lib/rbutils/graph/dijkstra.rb, line 6
def initialize(graph, source)

  #init variables
  @graph = graph
  @source = source
  @path = {}
  @dist_to = {}
  @queue = PriorityQueue.new

  #compute the shortest path
  computeSP
end

Public Instance Methods

computeSP() click to toggle source

Computer the shortest path source the source and Every other node

# File lib/rbutils/graph/dijkstra.rb, line 35
def computeSP
  @graph.nodes.each do |node|
    @dist_to[node]=Float::INFINITY
  end
  @dist_to[@source] = 0
  
  #node and it's distance to source (source -> source = 0)
  @queue.insert(@source, 0)
  
  #while elements exist in the queue
  while @queue.any?
    #check the lowest distance (closest)
    close = @queue.remove_min
    #check each adjacent edge
    close.adjacent_edges.each do |adjacent|
      relax(adjacent)
    end
  end
end
path_to(node) click to toggle source
# File lib/rbutils/graph/dijkstra.rb, line 19
def path_to(node)
  path = []
  while node != @source
    #add node to the front of the path
    path.unshift(node)
    node = @path[node]
  end
  #add the source at the beginning
  #invariant: source is at the front
  # and remaining nodes in the path are behind it
  # (reverse order)
  path.unshift(@source)
end
relax(edge) click to toggle source

Check if the shortest known path is still the shortest path That is, are there any shorter paths along this edge?

# File lib/rbutils/graph/dijkstra.rb, line 57
def relax(edge)
  #If the distance currently is lower than the added distance,
  #Don't increase it.
  return if @dist_to[edge.dest] <= @dist_to[edge.source] + edge.weight
  
  #Update the distance and add it back to the queue
  @dist_to[edge.dest] = @dist_to[edge.source] + edge.weight
  @path[edge.dest] = edge.source
  @queue.insert(edge.dest, @dist_to[edge.dest])
end