BellmanFord: The Bellman-Ford algorithm.

In robert-horne/SPAP: Solving Shortest Path Problems

Description

This Bellman-Ford implementation solves the Shortest Path Problem (SPP), requiring an adjacency matrix and a source node to be supplied, creating an object of class Bellman-Ford with the solution stored within, this can the be accessed by printing the object or plotting it, for the raw solution data use the class method getPrev(). The Bellman-Ford algorithm discovers negative cycles reachable from the source and reports them.

The graph class has the following class methods:

• getAdjMatrix() - Returns the adjacency matrix supplied to the algorithm.

• getDist() - Returns the matrix of distances from the source to each node at each iteration.

• getPrev() - Returns the matrix of previous nodes for every node at each iteration.

• negCycleExists() - Returns TRUE if the algorithm found a negative cycle reachable from the source.

• getNegCycle() - If a negative cycle was found it can be accessed using this method.

Usage

BellmanFord(matrix,1)

Arguments

adjMatrix	The ajacency matrix representing the graph to be solved, instead of a matrix the graph class can be supplied, and the adjacency matrix will be extracted.
sourceNode	The source node, corresponds to the node's row in the matrix supplied. Default is 1.

Examples

## Not run: 
  solution <- BellmanFord(matrix,1)
  print(solution)
  plot(solution)
  
## End(Not run)

robert-horne/SPAP documentation built on May 21, 2019, 10:09 a.m.