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