BellmanFordAlgorithm - Maple Help
For the best experience, we recommend viewing online help using Google Chrome or Microsoft Edge.

Online Help

All Products    Maple    MapleSim


GraphTheory

  

BellmanFordAlgorithm

  

find least-weight path using Bellman-Ford algorithm

 

Calling Sequence

Parameters

Description

Examples

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 weighted path of minimum weight 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  where  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  , 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

(1)

(2)

(3)

(4)

(5)

See Also

AllPairsDistance

DijkstrasAlgorithm

ShortestPath

 


Download Help Document