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.

$\mathrm{with}\left(\mathrm{GraphTheory}\right)\:$

$\mathrm{C6}≔\mathrm{Graph}\left(\left\{\left[\left\{1\,2\right\}\,1\right]\,\left[\left\{1\,6\right\}\,3\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]\right\}\right)$

$\mathrm{C6}≔\mathrm{Graph\; 1:\; an\; undirected\; weighted\; graph\; with\; 6\; vertices\; and\; 6\; edge(s)}$

$\mathrm{DijkstrasAlgorithm}\left(\mathrm{C6}\,1\,4\right)$

$\left[\left[1\,6\,5\,4\right]\,9\right]$

$\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]$

$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(s)}$

$\mathrm{DrawGraph}\left(G\right)$

$\mathrm{DijkstrasAlgorithm}\left(G\,1\,3\right)$

$\left[\left[1\,3\right]\,2\right]$

$\mathrm{DijkstrasAlgorithm}\left(G\,4\,6\right)$

$\left[\left[4\,5\,6\right]\,4\right]$

$\mathrm{DijkstrasAlgorithm}\left(G\,1\,6\right)$

$\left[\left[\right]\,\mathrm{\infty }\right]$