bellmanFord: Bellman-Ford Algorithm

In huoston/shortestpath: Shortest Path Algorithm Visualization

Description

Use the Bellman-Ford algorithm to calculate the shortest path from a source vertex to a target vertex in a directed, weighted graph

Usage

bellmanFord(graph, from, to)

Arguments

graph	The igraph object.
from	Source node
to	Target node

Details

The Bellman-Ford algorithm is a single source algorithm which can in contrast to the Dijkstra's and A*-Search algorithms deal with negative edge weights (Note in order to find the right shortest path it is required that no negative-weight cycle exist in the graph). The algorithm automatically detects cycles with a negative weight and shows a corresponding error message.

Like Dijkstra, the algorithm is based on the principle of relaxation. While Dijkstra selects the vertex with the minimum distance, the Bellman-Ford algorithm simply relaxes all the edges (#V-1 times). Thus, Bellman-Ford has a runtime of #V * #E.

Value

An spresults object.

Examples

g <- randomGraph(6, euclidean=FALSE)

bf <- bellmanFord(g, "A", "F")

plot(bf)

for(step in bf){
     print(step$min_dists)
}

huoston/shortestpath documentation built on May 25, 2019, 8:18 a.m.