# Class: RGL::DijkstraAlgorithm

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

## Constant Summary collapse

DEFAULT_DISTANCE_COMBINATOR =

Distance combinator is a lambda that accepts the distance (usually from the source) to vertex u and the weight of the edge connecting vertex u to another vertex v and returns the distance to vertex v if it’s reached through the vertex u. By default, the distance to vertex u and the edge’s weight are summed.

`lambda { |distance, edge_weight| distance + edge_weight }`

## Instance Method Summary collapse

• Finds the shortest path from the source to every other vertex.

• constructor

Initializes Dijkstra’s algorithm for a graph with provided edges weights map.

• Finds the shortest path from the source to the target in the graph.

• Finds the shortest path form the source to every other vertex of the graph and builds shortest paths map.

## Constructor Details

### #initialize(graph, edge_weights_map, visitor, distance_combinator = nil) ⇒ DijkstraAlgorithm

Initializes Dijkstra’s algorithm for a graph with provided edges weights map.

 ``` 19 20 21 22 23 24``` ```# File 'lib/rgl/dijkstra.rb', line 19 def initialize(graph, edge_weights_map, visitor, distance_combinator = nil) @graph = graph @edge_weights_map = build_edge_weights_map(edge_weights_map) @visitor = visitor @distance_combinator = distance_combinator || DEFAULT_DISTANCE_COMBINATOR end```

## Instance Method Details

### #find_shortest_paths(source) ⇒ Object

Finds the shortest path from the source to every other vertex.

 ``` 48 49 50 51``` ```# File 'lib/rgl/dijkstra.rb', line 48 def find_shortest_paths(source) init(source) relax_edges end```

### #shortest_path(source, target) ⇒ Object

Finds the shortest path from the source to the target in the graph.

Returns the shortest path, if it exists, as an Array of vertices. Otherwise, returns nil.

 ``` 30 31 32 33 34``` ```# File 'lib/rgl/dijkstra.rb', line 30 def shortest_path(source, target) init(source) relax_edges(target, true) PathBuilder.new(source, @visitor.parents_map).path(target) end```

### #shortest_paths(source) ⇒ Object

Finds the shortest path form the source to every other vertex of the graph and builds shortest paths map.

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

 ``` 41 42 43 44``` ```# File 'lib/rgl/dijkstra.rb', line 41 def shortest_paths(source) find_shortest_paths(source) PathBuilder.new(source, @visitor.parents_map).paths(@graph.vertices) end```