BellmanFordAlgorithm - Maple Help

GraphTheory

 BellmanFordAlgorithm
 find least-weight path using 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 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 $\left[\left[s,\mathrm{...},t\right],w\right]$ where $\left[s,\mathrm{...},t\right]$ is the path and w is the weight of that path.  If no such path exists the output is $\left[\left[\right],\mathrm{\infty }\right]$.
 • In the second calling sequence where T is a list of vertices of G, this is short for $\left[\mathrm{seq}\left(\mathrm{BellmanFordAlgorithm}\left(G,s,t\right),t=T\right)\right]$ , 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

 > $\mathrm{with}\left(\mathrm{GraphTheory}\right):$
 > $\mathrm{C6}≔\mathrm{Graph}\left(\left\{\left[\left[1,2\right],1\right],\left[\left[1,5\right],4\right],\left[\left[2,3\right],-3\right],\left[\left[3,4\right],7\right],\left[\left[5,6\right],-1\right],\left[\left[6,4\right],3\right]\right\}\right)$
 ${\mathrm{C6}}{≔}{\mathrm{Graph 1: a directed weighted graph with 6 vertices and 6 arc\left(s\right)}}$ (1)
 > $\mathrm{BellmanFordAlgorithm}\left(\mathrm{C6},1,4\right)$
 $\left[\left[{1}{,}{2}{,}{3}{,}{4}\right]{,}{5}\right]$ (2)
 > $\mathrm{BellmanFordAlgorithm}\left(\mathrm{C6},2,5\right)$
 $\left[\left[\right]{,}{\mathrm{\infty }}\right]$ (3)
 > $\mathrm{DrawGraph}\left(\mathrm{C6}\right)$
 > $\mathrm{BellmanFordAlgorithm}\left(\mathrm{C6},1\right)$
 $\left[\left[\left[{1}\right]{,}{0}\right]{,}\left[\left[{1}{,}{2}\right]{,}{1}\right]{,}\left[\left[{1}{,}{2}{,}{3}\right]{,}{-2}\right]{,}\left[\left[{1}{,}{2}{,}{3}{,}{4}\right]{,}{5}\right]{,}\left[\left[{1}{,}{5}\right]{,}{4}\right]{,}\left[\left[{1}{,}{5}{,}{6}\right]{,}{3}\right]\right]$ (4)
 > $\mathrm{BellmanFordAlgorithm}\left(\mathrm{C6},2\right)$
 $\left[\left[\left[\right]{,}{\mathrm{\infty }}\right]{,}\left[\left[{2}\right]{,}{0}\right]{,}\left[\left[{2}{,}{3}\right]{,}{-3}\right]{,}\left[\left[{2}{,}{3}{,}{4}\right]{,}{4}\right]{,}\left[\left[\right]{,}{\mathrm{\infty }}\right]{,}\left[\left[\right]{,}{\mathrm{\infty }}\right]\right]$ (5)