class Graphlb::Algorithms::BellmanFord

Overview

Bellman Ford's algorithm is an algorithm for finding the shortest paths between nodes in a graph,

Given a graph and source vertex Bellman Fords algorithm finds the shortest distance from the source vertex to all other vertices in the graph.

It also finds wheather a negative cycle is present in a graph or not

.new(graph, source)
Runs the Bellman_Ford Algorithm on the given graph and the source node

#shortest_path(source, target)
constructs a path from source vertex to target vertex
#shortest_paths(source)
constructs a path from source vertex to all other vertices in the graph

def self.new(graph, source) #

Runs the Bellman_Ford Algorithm on the given graph and the source node

If the graph contains a negative cycle it returns an exception

@param : graph, A directed graph

@param : Source, Source vertex form which the algorithm starts running

[View source]

def shortest_path(source, target) #

constructs a path from source vertex to target vertex

@param : Source, the source vertex for the path

@param : target, The vertex till which the path should be constructed

@return : An array which contains all the vertices(path) to be travelled to reach from source to target vertex

[View source]

def shortest_paths(source) #

constructs a path from source vertex to all other vertices in the graph

@param : Source, the source vertex for the path

@return : An array which contains all the vertices(path) to be travelled to reach from source vertex to all other vertices in the graph

[View source]