spTreeBellmanFord
function computes the shortest
path tree of an undirected or directed graph with the
Bellman-Ford algorithm.
spTreeBellmanFord(nodes, arcs, source.node = 1, directed = TRUE)
TRUE
) or not (FALSE
).spTreeBellmanFord
returns a list with:The Bellman-Ford algorithm can compute the shortest path from a source node to the rest of nodes that make a connected graph, directed or not, with weights that can be negatives. If the graph is connected and there isn't negative cycles, the algorithm always finds a shortest path tree.
Ford Jr., Lester R. (1956). Network Flow Theory. Paper P-923. Santa Monica, California: RAND Corporation.
Moore, Edward F. (1959). "The shortest path through a maze". Proc. Internat. Sympos. Switching Theory 1957, Part II. Cambridge, Mass.: Harvard Univ. Press. pp. 285-292.