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 36 def initialize(graph, edge_weights_map, visitor) 37 @graph = graph 38 @edge_weights_map = EdgePropertiesMap.new(edge_weights_map, @graph.directed?) 39 @visitor = visitor 40 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 47 def shortest_paths(source) 48 init(source) 49 relax_edges 50 PathBuilder.new(source, @visitor.parents_map).paths(@graph.vertices) 51 end
Private Instance Methods
init(source)
click to toggle source
# File lib/rgl/bellman_ford.rb 55 def init(source) 56 @visitor.set_source(source) 57 end
relax_edge(u, v)
click to toggle source
# File lib/rgl/bellman_ford.rb 76 def relax_edge(u, v) 77 @visitor.handle_examine_edge(u, v) 78 79 new_v_distance = @visitor.distance_map[u] + @edge_weights_map.edge_property(u, v) 80 81 if new_v_distance < @visitor.distance_map[v] 82 @visitor.distance_map[v] = new_v_distance 83 @visitor.parents_map[v] = u 84 85 @visitor.handle_edge_relaxed(u, v) 86 else 87 @visitor.handle_edge_not_relaxed(u, v) 88 end 89 end
relax_edges()
click to toggle source
# File lib/rgl/bellman_ford.rb 59 def relax_edges 60 (@graph.size - 1).times do 61 @graph.each_edge do |u, v| 62 relax_edge(u, v) 63 relax_edge(v, u) unless @graph.directed? 64 end 65 end 66 67 @graph.each_edge do |u, v| 68 if @visitor.distance_map[u] + @edge_weights_map.edge_property(u, v) < @visitor.distance_map[v] 69 @visitor.handle_edge_not_minimized(u, v) 70 else 71 @visitor.handle_edge_minimized(u, v) 72 end 73 end 74 end