find the cheapest weighted path using the Bellman-Ford algorithm - Maple Help

Online Help

All Products    Maple    MapleSim


Home : Support : Online Help : Mathematics : Discrete Mathematics : Graph Theory : GraphTheory Package : GraphTheory/BellmanFordAlgorithm

GraphTheory[BellmanFordAlgorithm] - find the cheapest weighted path using the Bellman-Ford algorithm

Calling Sequence

BellmanFordAlgorithm(G, s, t)

BellmanFordAlgorithm(G, s, T)

BellmanFordAlgorithm(G, s)

Parameters

G

-

a graph, unweighted, or weighted with no negative cycles

s, t

-

vertices of the graph G

T

-

list of vertices of the graph G

Description

• 

The BellmanFordAlgorithm uses the Bellman-Ford algorithm to find the cheapest weighted path from s to t.

• 

If G is an unweighted graph, the edges are assumed all to have weight 1.

• 

If G is a weighted graph, BellmanFordAlgorithm(G,s,t) returns the cheapest weighted path from vertex s to vertex t in the graph G. If a path from s to t exists, the output is a list of the form s,...,t,w where s,...,t is the path and w is the weight of that path.  If no such path exists the output is ,.

• 

In the second calling sequence where T is a list of vertices of G, this is short for seqBellmanFordAlgorithmG,s,t,t=T , except that the algorithm does not need to recompute cheapest paths.

• 

In the third calling sequence where no destination vertices are given, this is short for BellmanFordAlgorithm(G,s, Vertices(G)), and the cheapest path from s to every vertex in G is output.

• 

To compute distances between all pairs of vertices simultaneously, use the AllPairsDistance command.  To ignore edge weights (and use a faster breadth-first search), use the ShortestPath command.  

• 

Note that G can have no negative cycles, which also means that any edges with negative weights must be directed (as otherwise the undirected negative weight edge forms a negative weight cycle between the vertices it connects). If G has no negative edge weights, DijkstrasAlgorithm may be able to find the cheapest paths more efficiently.

Examples

withGraphTheory:

C6:=Graph1,2,1,2,3,3,3,4,7,1,5,4,5,6,1,6,4,3

C6:=Graph 1: a directed weighted graph with 6 vertices and 6 arc(s)

(1)

BellmanFordAlgorithmC6,1,4

1,2,3,4,5

(2)

BellmanFordAlgorithmC6,2,5

,∞

(3)

DrawGraphC6

BellmanFordAlgorithmC6,1

1,0,1,2,1,1,2,3,2,1,2,3,4,5,1,5,4,1,5,6,3

(4)

BellmanFordAlgorithmC6,2

,∞,2,0,2,3,3,2,3,4,4,,∞,,∞

(5)

See Also

AllPairsDistance, DijkstrasAlgorithm, ShortestPath


Download Help Document

Was this information helpful?



Please add your Comment (Optional)
E-mail Address (Optional)
What is ? This question helps us to combat spam