class Graphlb::Algorithms::Dijkstras

Overview

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

Given a graph and source vertex dijkstra function finds the shortest distance from the source vertex to all other vertices in the graph

.new(graph, source)
Runs the Dijkstras 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 Dijkstras Algorithm on the given graph and the source node

@param : graph, A directed graph,

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

@raise : it raises an exception when there is a negative edge in the graph

[View source]

def shortest_path(source, target) #

constructs a path from source vertex to target vertex

@param : prev , prev hash contains the previous node of all the vertices

@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]