Maple Student Edition
Maple Personal Edition
Maple Player for iPad
Maple T.A. - Testing & Assessment
Maple T.A. MAA Placement Test Suite
Möbius - Online Courseware
Machine Design / Industrial Automation
System Simulation and Analysis
Model development for HIL
Plant Modeling for Control Design
Other Application Areas
High Schools & Two-Year Colleges
Testing & Assessment
High Performance Computing
Maple Ambassador Program
MapleSim Model Gallery
User Case Studies
Exploring Engineering Fundamentals
Teaching Concepts with Maple
Maplesoft Welcome Center
Teacher Resource Center
Student Help Center
GraphTheory[BellmanFordAlgorithm] - find the cheapest weighted path using the Bellman-Ford algorithm
BellmanFordAlgorithm(G, s, t)
BellmanFordAlgorithm(G, s, T)
a graph, unweighted, or weighted with no negative cycles
vertices of the graph G
list of vertices of the graph G
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 seq⁡BellmanFordAlgorithmG,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.
C6:=Graph 1: a directed weighted graph with 6 vertices and 6 arc(s)
AllPairsDistance, DijkstrasAlgorithm, ShortestPath
Download Help Document