bellman.ford.sp
BellmanFord shortest paths using boost C++
Algorithm for the singlesource shortest paths problem for a graph with both positive and negative edge weights.
 Keywords
 graphs
Usage
bellman.ford.sp(g,start=nodes(g)[1])
Arguments
 g
 instance of class graph
 start
 character: node name for start of path
Details
This function interfaces to the Boost graph library C++ routines for BellmanFord shortest paths. Choose the appropriate algorithm to calculate the shortest path carefully based on the properties of the given graph. See documentation on BellmanFord algorithm in Boost Graph Library for more details.
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 ofg
; includesInf
when there is no path fromstart
.  penult
 A vector of indices
(in
nodes(g)
) of predecessors corresponding to each node on the path from that node back tostart
. For example, if the
element one of this vector has value  start
 The start node that was supplied in the call to
bellman.ford.sp
.
10
, that means that the
predecessor of node 1
is node 10
. The next predecessor is
found by examining penult[10]
.
References
Boost Graph Library ( www.boost.org/libs/graph/doc/index.html )
The Boost Graph Library: User Guide and Reference Manual; by Jeremy G. Siek, LieQuan Lee, and Andrew Lumsdaine; (AddisonWesley, Pearson Education Inc., 2002), xxiv+321pp. ISBN 0201729148
See Also
Examples
con < file(system.file("XML/conn2.gxl",package="RBGL"), open="r")
dd < fromGXL(con)
close(con)
bellman.ford.sp(dd)
bellman.ford.sp(dd,nodes(dd)[2])
Community examples
Looks like there are no examples yet.