bellman.ford.sp {RBGL}R Documentation

Bellman-Ford shortest paths using boost C++

Description

Algorithm for the single-source shortest paths problem for a graph with both positive and negative edge weights.

Usage

bellman.ford.sp(g,start=nodes(g)[1])

Arguments

g instance of class graph
start character: node name for start of path

Details

These functions are interfaces to the Boost graph library C++ routines for Bellman-Ford shortest paths. If you only need to solve the shortest paths problem for positive edge weights, Dijkstra's algorithm provides a more efficient alternative. If all the edge weights are all equal to one then breadth-first search provides an even more efficient alternative. If there is a negative cycle in the graph, then there will be edges in the graph that were not properly minimized. The algorithm loops over the edges in the graph one final time to check if all the edges were minimized, returning true if they were and returning false otherwise.

Value

A list with elements:

all edges minimized true if all edges are minimized, false otherwise.
distance The vector of distances from start to each node of g; includes Inf when there is no path from start.
penult A vector of indices (in nodes(g)) of predecessors corresponding to each node on the path from that node back to start
start The start node that was supplied in the call to bellman.ford.sp.

Author(s)

Li Long <li.long@isb-sib.ch>

See Also

Examples

dd <- fromGXL(file(system.file("XML/conn2.gxl",package="RBGL")))
bellman.ford.sp(dd)
bellman.ford.sp(dd,nodes(dd)[2])

[Package RBGL version 1.3.8 Index]