# Distances, Shortest Paths and Minimum Weight Trees

Two standard algorithms have been implemented for finding single-source shortest paths in weighted graphs. One is Dijsktra’s algorithm for graphs without negative weight cycles, the second is Bellman-Ford’s for those graphs with negative weight cycles. Dijsktra’s algorithm is implemented either by a priority queue (binary heap) or a Fibonacci heap. The Fibonacci heap is asymptotically faster for sparse graphs. But for most practical purposes (graphs of small order) the binary heap outperforms the Fibonacci heap and is therefore chosen as the default data structure wherever relevant.

Johnson’s algorithm has been chosen for the all-pairs shortest paths computation. Indeed, it outperforms the simpler Floyd’s algorithm, especially as the graphs get larger.

Finally, Prim’s algorithm is used to implement the minimum weight tree computation for undirected graphs. (The tree is a spanning tree if and only if the graph is connected.)

All the functions described below apply to general graphs whose edges are assigned a weight. If the graph under consideration is not weighted, then all its edges are assumed to have weight one. To assign weights to the edges of a graph, see Subsection [Edge Decorations](multig-decorations.md#multigraph-subsec-edge-decs). Note that all the functions described below accept negatively weighted edges.

## `Reachable(u, v : parameters): GrphVert, GrphVert -> BoolElt, RngElt`

```magma
UseFibonacciHeap: Bool                    Default: false
```

Return `true` if and only there is a path from vertex $u$ to vertex $v$. If true, also returns the distance between $u$ and $v$.

## `Distance(u, v : parameters): GrphVert, GrphVert -> RngElt`

```magma
UseFibonacciHeap: Bool                    Default: false
```

Given vertices $u$ and $v$ in a graph $G$, computes the distance from $u$ to $v$. Results in an error if there is no path in $G$ from $u$ to $v$.

## `Distances(u : parameters): GrphVert -> Eseq`

```magma
UseFibonacciHeap: Bool                    Default: false
```

Given a vertex $u$ in a graph $G$, computes the sequence $D$ of distances from $u$ to $v$, $v$ any vertex in $G$. Given any vertex $v$ in $G$, let $i$ be `Index(v)`. Then $D[i]$, if defined, is the distance from $u$ to $v$. If there is no path from $u$ to $v$, then the sequence element $D[i]$ is undefined.

## `PathExists(u, v : parameters): GrphVert, GrphVert -> BoolElt, Eseq`

```magma
UseFibonacciHeap: Bool                    Default: false
```

Return `true` if and only there is a path from vertex $u$ to vertex $v$ in the parent graph $G$. If so, also returns a shortest path from $u$ to $v$ as a sequence of edges of $G$.

## `Path(u, v : parameters): GrphVert, GrphVert -> Eseq`

## `ShortestPath(u, v : parameters): GrphVert, GrphVert -> Eseq`

```magma
UseFibonacciHeap: Bool                    Default: false
```

Given vertices $u$ and $v$ in a graph $G$, computes a shortest path from $u$ to $v$ as a sequence of edges of $G$. Results in an error if there is no path in $G$ from $u$ to $v$.

## `Paths(u : parameters): GrphVert -> Eseq`

## `ShortestPaths(u : parameters): GrphVert -> Eseq`

```magma
UseFibonacciHeap: Bool                    Default: false
```

Given a vertex $u$ in a graph $G$, computes the sequence $P$ of shortest paths from $u$ to $v$, for every vertex $v$ in $G$. Given any vertex $v$ in $G$, let $i$ be `Index(v)`. If there exists a path from $u$ to $v$ then $P[i]$ is a sequence of edges giving a shortest path from $u$ to $v$. If there is no path from $u$ to $v$, then the sequence element $P[i]$ is undefined.

## `GeodesicExists(u, v : parameters): GrphVert, GrphVert -> BoolElt, Eseq`

```magma
UseFibonacciHeap: Bool                    Default: false
```

Return `true` if and only there is a path from vertex $u$ to vertex $v$ in the parent graph $G$. If true, also returns a shortest path from $u$ to $v$ as a sequence of vertices of $G$.

## `Geodesic(u, v : parameters): GrphVert, GrphVert -> Eseq`

```magma
UseFibonacciHeap: Bool                    Default: false
```

Given vertices $u$ and $v$ in a graph $G$, this function computes a shortest path from $u$ to $v$ as a sequence of vertices of $G$. An error results if there is no path in $G$ from $u$ to $v$.

## `Geodesics(u : parameters): GrphVert -> Eseq`

```magma
UseFibonacciHeap: Bool                    Default: false
```

Given a vertex $u$ in a graph $G$, this function computes the sequence $P$ of shortest paths from $u$ to $v$, for every vertex $v$ in $G$. Given any vertex $v$ in $G$, let $i$ be `Index(v)`. If there exists a path from $u$ to $v$ then $P[i]$ is a sequence of vertices specifying a shortest path from $u$ to $v$. If there is no path from $u$ to $v$, then the sequence element $P[i]$ is undefined.

## `HasNegativeWeightCycle(u : parameters): GrphVert -> BoolElt`

Return `true` if and only if there is a negative-weight cycle reachable from vertex $u$.

## `HasNegativeWeightCycle(G): Grph -> BoolElt`

## `HasNegativeWeightCycle(G): GrphMult -> BoolElt`

Return `true` if and only if the graph $G$ has negative-weight cycles.

## `AllPairsShortestPaths(G : parameters): Grph -> SeqEnum, SeqEnum`

## `AllPairsShortestPaths(G : parameters): GrphMult -> SeqEnum, SeqEnum`

```magma
UseFibonacciHeap: Bool                    Default: false
```

Computes the all-pairs shortest paths. Let $u$ and $v$ be two vertices of a graph $G$ and let $i = {\sl Index(u)}$ and $j = {\sl Index(v)}$. Let $S_1$ and $S_2$ be the two sequences returned by `AllPairsShortestPaths`, and let $s_1 = S_1[i]$ and $s_2 = S_2[i]$. Then $s_1[j]$, if defined, gives the distance from $u$ to $v$ and $s_2[j]$, if defined, gives the vertex preceding $v$ in the shortest path from $u$ to $v$. An error results if the graph $G$ has a negative-weight cycle.

## `MinimumWeightTree(u : parameters): GrphVert -> SeqEnum`

```magma
UseFibonacciHeap: Bool                    Default: false
```

Returns a minimum weight tree rooted at vertex $u$, $u$ any vertex of an *undirected* graph $G$, as a subgraph of $G$. The tree spans $G$ if and only if $G$ is connected. The support of $G$ as well as the vertex and edge decorations in $G$ *are* transferred to the tree.

## `Example: GrphMult ShortP (ex-549372)`

We create a weighted multidigraph.

```magma
> G := MultiDigraph< 5 | [1, 2], [1, 2], [1, 3], [2, 4], [3, 5], [3, 4], [4, 5] >;
> E := EdgeSet(G);
> AssignWeight(~G, E.1, 1);
> AssignWeight(~G, E.2, 5);
> AssignWeight(~G, E.3, 10);
> AssignWeight(~G, E.4, 1);
> AssignWeight(~G, E.5, -5);
> AssignWeight(~G, E.6, 1);
> AssignWeight(~G, E.7, 2);
>
>
> V := VertexSet(G);
> E := EdgeSet(G);
> for e in E do
>     e, "  ", Weight(e);
> end for;
< [1, 3], 3 >    10
< [1, 2], 2 >    5
< [1, 2], 1 >    1
< [2, 4], 4 >    1
< [3, 4], 6 >    1
< [3, 5], 5 >    -5
< [4, 5], 7 >    2

```

We verify that it has no negative weight cycle reachable from vertex 1, and that there is a path from vertex 1 to vertex 5.

```magma
> HasNegativeWeightCycle(V!1);
false
> b, d := Reachable(V!1, V!5);
> assert b;
> P := Path(V!1, V!5);
> G := Geodesic(V!1, V!5);
>
> d;
4
> P;
[ < [1, 2], 1 >, < [2, 4], 4 >, < [4, 5], 7 > ]
> G;
[ 1, 2, 4, 5 ]

```

Finally, we verify that the shortest path found has length 4.

```magma
> dP := 0;
> for e in P do
>     dP +:= Weight(e);
> end for;
> assert dP eq d;

```

Note that had we taken instead an undirected graph, we would have had to assign only positive weights to the edges of the graph: any undirected edge $\{u, v\}$ with negative weight results in the negative weight cycles $\{u, u\}$ and $\{v, v\}$.

## `Example: GrphMult MinW (ex-8c3a20)`

We create a weighted multigraph with one edge assigned a negative weight.

```magma
> G := MultiGraph< 5 | {1, 2}, {1, 2}, {1, 3}, {2, 4}, {3, 5}, {3, 4}, {4, 5} >;
> E := EdgeSet(G);
> AssignWeight(~G, E.1, 1);
> AssignWeight(~G, E.3, 5);
> AssignWeight(~G, E.5, 10);
> AssignWeight(~G, E.7, 1);
> AssignWeight(~G, E.9, -5);
> AssignWeight(~G, E.11, 1);
> AssignWeight(~G, E.13, 2);
>
> V := VertexSet(G);
> E := EdgeSet(G);
> for e in E do
>     e, "  ", Weight(e);
> end for;
< {1, 3}, 5 >    10
< {1, 2}, 3 >    5
< {1, 2}, 1 >    1
< {2, 4}, 7 >    1
< {3, 4}, 11 >    1
< {3, 5}, 9 >    -5
< {4, 5}, 13 >    2

```

We compute a minimum weight spanning tree rooted at vertex 1.

```magma
> T := MinimumWeightTree(V!1);
> ET := EdgeSet(T);
> for e in ET do
>     e, "  ", Weight(e);
> end for;
< {1, 2}, 1 >    1
< {2, 4}, 5 >    1
< {3, 5}, 7 >    -5
< {3, 4}, 3 >    1

```

We compute any other spanning tree rooted at vertex 1 (say a depth first tree using [`DFSTree`](spanning-tree.md#function-multigraph-dfstree)), and verify that the weights of the edges in $G$ corresponding to the edges of the tree sum up to a total weight which is no smaller than the weight of the minimum weight spanning tree.

```magma
> DFST := DFSTree(V!1);
> EDT := EdgeSet(DFST);
> for e in EDT do
>     u := InitialVertex(e);
>     v := TerminalVertex(e);
>     w := Min([ Weight(edge) : edge in Edges(V!u, V!v) ]);
>     e, "  ", w;
> end for;
< {1, 3}, 1 >    10
< {2, 4}, 7 >    1
< {3, 4}, 3 >    1
< {4, 5}, 5 >    2

```