Class: RGL::BellmanFordAlgorithm

Inherits:
Object
  • Object
show all
Defined in:
lib/rgl/bellman_ford.rb

Overview

This class implements Graph#bellman_ford_shortest_paths.

Instance Method Summary collapse

Constructor Details

#initialize(graph, edge_weights_map, visitor) ⇒ BellmanFordAlgorithm

Initializes Bellman-Ford algorithm for a graph with provided edges weights map.



35
36
37
38
39
 
# File 'lib/rgl/bellman_ford.rb', line 35

def initialize(graph, edge_weights_map, visitor)
  @graph            = graph
  @edge_weights_map = EdgePropertiesMap.new(edge_weights_map, @graph.directed?)
  @visitor          = visitor
end

Instance Method Details

#shortest_paths(source) ⇒ Hash[Object,Array]

Finds the shortest path form the source to every other vertex of the graph.

Returns the shortest paths map that contains the shortest path (if it exists) from the source to any vertex of the graph.

Returns:

  • (Hash[Object,Array]) 


47
48
49
50
51
 
# File 'lib/rgl/bellman_ford.rb', line 47

def shortest_paths(source)
  init(source)
  relax_edges
  PathBuilder.new(source, @visitor.parents_map).paths(@graph.vertices)
end