class RGL::BellmanFordAlgorithm
Public Class Methods
new(graph, edge_weights_map, visitor)
click to toggle source
Initializes Bellman-Ford algorithm for a graph with provided edges weights map.
# File lib/rgl/bellman_ford.rb, line 36 def initialize(graph, edge_weights_map, visitor) @graph = graph @edge_weights_map = EdgePropertiesMap.new(edge_weights_map, @graph.directed?) @visitor = visitor end
Public Instance Methods
shortest_paths(source)
click to toggle source
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.
# 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
Private Instance Methods
init(source)
click to toggle source
# File lib/rgl/bellman_ford.rb, line 55 def init(source) @visitor.set_source(source) end
relax_edge(u, v)
click to toggle source
# File lib/rgl/bellman_ford.rb, line 76 def relax_edge(u, v) @visitor.handle_examine_edge(u, v) new_v_distance = @visitor.distance_map[u] + @edge_weights_map.edge_property(u, v) if new_v_distance < @visitor.distance_map[v] @visitor.distance_map[v] = new_v_distance @visitor.parents_map[v] = u @visitor.handle_edge_relaxed(u, v) else @visitor.handle_edge_not_relaxed(u, v) end end
relax_edges()
click to toggle source
# File lib/rgl/bellman_ford.rb, line 59 def relax_edges (@graph.size - 1).times do @graph.each_edge do |u, v| relax_edge(u, v) relax_edge(v, u) unless @graph.directed? end end @graph.each_edge do |u, v| if @visitor.distance_map[u] + @edge_weights_map.edge_property(u, v) < @visitor.distance_map[v] @visitor.handle_edge_not_minimized(u, v) else @visitor.handle_edge_minimized(u, v) end end end