GraphTheory - Maple Programming Help

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

GraphTheory

 DijkstrasAlgorithm

 Calling Sequence DijkstrasAlgorithm(G, s, t) DijkstrasAlgorithm(G, s, T) DijkstrasAlgorithm(G, s)

Parameters

 G - a graph with non-negative edge weights or no weights s, t - vertices of the graph G T - list of vertices of the graph G

Description

 • If G is an unweighted graph, the edges are assumed all to have weight 1.
 • If G is a weighted graph, DijkstrasAlgorithm('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 $\left[\left[\right],\mathrm{\infty }\right]$.
 • In the second calling sequence where T is a list of vertices of G, this is short for [seq(DijkstrasAlgorithm(G,s,t), t=T)], save 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 DijkstrasAlgorithm(G,s,Vertices(G)), i.e. 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.
 • If some edge weights are negative, the BellmanFordAlgorithm command can be used to compute the shortest path.

Examples

 > $\mathrm{with}\left(\mathrm{GraphTheory}\right):$
 > $\mathrm{C6}≔\mathrm{Graph}\left(\left\{\left[\left\{1,2\right\},1\right],\left[\left\{2,3\right\},3\right],\left[\left\{3,4\right\},7\right],\left[\left\{4,5\right\},3\right],\left[\left\{5,6\right\},3\right],\left[\left\{1,6\right\},3\right]\right\}\right)$
 ${\mathrm{C6}}{≔}{\mathrm{Graph 1: an undirected weighted graph with 6 vertices and 6 edge\left(s\right)}}$ (1)
 > $\mathrm{DijkstrasAlgorithm}\left(\mathrm{C6},1,4\right)$
 $\left[\left[{1}{,}{6}{,}{5}{,}{4}\right]{,}{9}\right]$ (2)
 > $\mathrm{DrawGraph}\left(\mathrm{C6}\right)$
 > $\mathrm{DijkstrasAlgorithm}\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]{,}{4}\right]{,}\left[\left[{1}{,}{6}{,}{5}{,}{4}\right]{,}{9}\right]{,}\left[\left[{1}{,}{6}{,}{5}\right]{,}{6}\right]{,}\left[\left[{1}{,}{6}\right]{,}{3}\right]\right]$ (3)
 > $G≔\mathrm{Graph}\left(\left\{\left[\left[1,2\right],2\right],\left[\left[1,3\right],2\right],\left[\left[2,3\right],2\right],\left[\left[3,1\right],2\right],\left[\left[4,5\right],2\right],\left[\left[5,6\right],2\right],\left[\left[6,4\right],2\right]\right\}\right)$
 ${G}{≔}{\mathrm{Graph 2: a directed weighted graph with 6 vertices and 7 arc\left(s\right)}}$ (4)
 > $\mathrm{DrawGraph}\left(G\right)$
 > $\mathrm{DijkstrasAlgorithm}\left(G,1,3\right)$
 $\left[\left[{1}{,}{3}\right]{,}{2}\right]$ (5)
 > $\mathrm{DijkstrasAlgorithm}\left(G,4,6\right)$
 $\left[\left[{4}{,}{5}{,}{6}\right]{,}{4}\right]$ (6)
 > $\mathrm{DijkstrasAlgorithm}\left(G,1,6\right)$
 $\left[\left[{}\right]{,}{\mathrm{∞}}\right]$ (7)