BellmanFord

BellmanFord[g, v]
gives a shortest-path spanning tree and associated distances from vertex

of graph

. The shortest-path spanning tree is given by a list in which element

is the predecessor of vertex

in the shortest-path spanning tree. BellmanFord works correctly even when the edge weights are negative, provided there are no negative cycles.

To use BellmanFord, you first need to load the Combinatorica Package using Needs["Combinatorica`"].