▸▿ Contents

Settings help

FL Name Style:

FL Specification Language:

1Purpose

h03adf finds the shortest path through a directed or undirected acyclic network using Dijkstra's algorithm.

2Specification

Fortran Interface
 Subroutine h03adf ( n, ns, ne, nnz, d, irow, icol, path, work,
 Integer, Intent (In) :: n, ns, ne, nnz, icol(nnz) Integer, Intent (Inout) :: irow(nnz), ifail Integer, Intent (Out) :: path(n), iwork(3*n+1) Real (Kind=nag_wp), Intent (In) :: d(nnz) Real (Kind=nag_wp), Intent (Out) :: splen, work(2*n) Logical, Intent (In) :: direct
#include <nag.h>
 void h03adf_ (const Integer *n, const Integer *ns, const Integer *ne, const logical *direct, const Integer *nnz, const double d[], Integer irow[], const Integer icol[], double *splen, Integer path[], Integer iwork[], double work[], Integer *ifail)
The routine may be called by the names h03adf or nagf_mip_shortestpath.

3Description

h03adf attempts to find the shortest path through a directed or undirected acyclic network, which consists of a set of points called vertices and a set of curves called arcs that connect certain pairs of distinct vertices. An acyclic network is one in which there are no paths connecting a vertex to itself. An arc whose origin vertex is $i$ and whose destination vertex is $j$ can be written as $i\to j$. In an undirected network the arcs $i\to j$ and $j\to i$ are equivalent (i.e., $i↔j$), whereas in a directed network they are different. Note that the shortest path may not be unique and in some cases may not even exist (e.g., if the network is disconnected).
The network is assumed to consist of $n$ vertices which are labelled by the integers $1,2,\dots ,n$. The lengths of the arcs between the vertices are defined by the $n×n$ distance matrix ${\mathbf{d}}$, in which the element ${d}_{ij}$ gives the length of the arc $i\to j$; ${d}_{ij}=0$ if there is no arc connecting vertices $i$ and $j$ (as is the case for an acyclic network when $i=j$). Thus the matrix $D$ is usually sparse. For example, if $n=4$ and the network is directed, then
 $d=( 0 d12 d13 d14 d21 0 d23 d24 d31 d32 0 d34 d41 d42 d43 0 ) .$
If the network is undirected, ${\mathbf{d}}$ is symmetric since ${d}_{ij}={d}_{ji}$ (i.e., the length of the arc $i\to j\equiv \text{}$ the length of the arc $j\to i$).
The method used by h03adf is described in detail in Section 9.

4References

Dijkstra E W (1959) A note on two problems in connection with graphs Numer. Math. 1 269–271

5Arguments

1: $\mathbf{n}$Integer Input
On entry: $n$, the number of vertices.
Constraint: ${\mathbf{n}}\ge 2$.
2: $\mathbf{ns}$Integer Input
3: $\mathbf{ne}$Integer Input
On entry: ${n}_{s}$ and ${n}_{e}$, the labels of the first and last vertices, respectively, between which the shortest path is sought.
Constraints:
• $1\le {\mathbf{ns}}\le {\mathbf{n}}$;
• $1\le {\mathbf{ne}}\le {\mathbf{n}}$;
• ${\mathbf{ns}}\ne {\mathbf{ne}}$.
4: $\mathbf{direct}$Logical Input
On entry: indicates whether the network is directed or undirected.
${\mathbf{direct}}=\mathrm{.TRUE.}$
The network is directed.
${\mathbf{direct}}=\mathrm{.FALSE.}$
The network is undirected.
5: $\mathbf{nnz}$Integer Input
On entry: the number of nonzero elements in the distance matrix $D$.
Constraints:
• if ${\mathbf{direct}}=\mathrm{.TRUE.}$, $1\le {\mathbf{nnz}}\le {\mathbf{n}}×\left({\mathbf{n}}-1\right)$;
• if ${\mathbf{direct}}=\mathrm{.FALSE.}$, $1\le {\mathbf{nnz}}\le {\mathbf{n}}×\left({\mathbf{n}}-1\right)/2$.
6: $\mathbf{d}\left({\mathbf{nnz}}\right)$Real (Kind=nag_wp) array Input
On entry: the nonzero elements of the distance matrix $D$, ordered by increasing row index and increasing column index within each row. More precisely, ${\mathbf{d}}\left(k\right)$ must contain the value of the nonzero element with indices (${\mathbf{irow}}\left(k\right),{\mathbf{icol}}\left(k\right)$); this is the length of the arc from the vertex with label ${\mathbf{irow}}\left(k\right)$ to the vertex with label ${\mathbf{icol}}\left(k\right)$. Elements with the same row and column indices are not allowed. If ${\mathbf{direct}}=\mathrm{.FALSE.}$, then only those nonzero elements in the strict upper triangle of ${\mathbf{d}}$ need be supplied since ${d}_{ij}={d}_{ji}$. (f11zaf may be used to sort the elements of an arbitrarily ordered matrix into the required form.)
Constraint: ${\mathbf{d}}\left(\mathit{k}\right)>0.0$, for $\mathit{k}=1,2,\dots ,{\mathbf{nnz}}$.
7: $\mathbf{irow}\left({\mathbf{nnz}}\right)$Integer array Input
8: $\mathbf{icol}\left({\mathbf{nnz}}\right)$Integer array Input
On entry: ${\mathbf{irow}}\left(k\right)$ and ${\mathbf{icol}}\left(k\right)$ must contain the row and column indices, respectively, for the nonzero element stored in ${\mathbf{d}}\left(k\right)$.
Constraints:
irow and icol must satisfy the following constraints (which may be imposed by a call to f11zaf):
• ${\mathbf{irow}}\left(k-1\right)<{\mathbf{irow}}\left(k\right)$;
• ${\mathbf{irow}}\left(\mathit{k}-1\right)={\mathbf{irow}}\left(\mathit{k}\right)$ and ${\mathbf{icol}}\left(\mathit{k}-1\right)<{\mathbf{icol}}\left(\mathit{k}\right)$, for $\mathit{k}=2,3,\dots ,{\mathbf{nnz}}$.
In addition, if ${\mathbf{direct}}=\mathrm{.TRUE.}$, $1\le {\mathbf{irow}}\left(k\right)\le {\mathbf{n}}$, $1\le {\mathbf{icol}}\left(k\right)\le {\mathbf{n}}$ and ${\mathbf{irow}}\left(k\right)\ne {\mathbf{icol}}\left(k\right)$;
• if ${\mathbf{direct}}=\mathrm{.FALSE.}$, $1\le {\mathbf{irow}}\left(k\right)<{\mathbf{icol}}\left(k\right)\le {\mathbf{n}}$.
9: $\mathbf{splen}$Real (Kind=nag_wp) Output
On exit: the length of the shortest path between the specified vertices ${n}_{s}$ and ${n}_{e}$.
10: $\mathbf{path}\left({\mathbf{n}}\right)$Integer array Output
On exit: contains details of the shortest path between the specified vertices ${n}_{s}$ and ${n}_{e}$. More precisely, ${\mathbf{ns}}={\mathbf{path}}\left(1\right)\to {\mathbf{path}}\left(2\right)\to \cdots \to {\mathbf{path}}\left(p\right)={\mathbf{ne}}$ for some $p\le n$. The remaining $\left(n-p\right)$ elements are set to zero.
11: $\mathbf{iwork}\left(3×{\mathbf{n}}+1\right)$Integer array Workspace
12: $\mathbf{work}\left(2×{\mathbf{n}}\right)$Real (Kind=nag_wp) array Workspace
13: $\mathbf{ifail}$Integer Input/Output
On entry: ifail must be set to $0$, $-1$ or $1$ to set behaviour on detection of an error; these values have no effect when no error is detected.
A value of $0$ causes the printing of an error message and program execution will be halted; otherwise program execution continues. A value of $-1$ means that an error message is printed while a value of $1$ means that it is not.
If halting is not appropriate, the value $-1$ or $1$ is recommended. If message printing is undesirable, then the value $1$ is recommended. Otherwise, the value $0$ is recommended. When the value $-\mathbf{1}$ or $\mathbf{1}$ is used it is essential to test the value of ifail on exit.
On exit: ${\mathbf{ifail}}={\mathbf{0}}$ unless the routine detects an error or a warning has been flagged (see Section 6).

6Error Indicators and Warnings

If on entry ${\mathbf{ifail}}=0$ or $-1$, explanatory error messages are output on the current error message unit (as defined by x04aaf).
Errors or warnings detected by the routine:
${\mathbf{ifail}}=1$
On entry, ${\mathbf{n}}=⟨\mathit{\text{value}}⟩$.
Constraint: ${\mathbf{n}}\ge 2$.
On entry, ${\mathbf{ne}}=⟨\mathit{\text{value}}⟩$ and ${\mathbf{n}}=⟨\mathit{\text{value}}⟩$.
Constraint: $1\le {\mathbf{ne}}\le {\mathbf{n}}$.
On entry, ${\mathbf{ns}}=⟨\mathit{\text{value}}⟩$ and ${\mathbf{n}}=⟨\mathit{\text{value}}⟩$.
Constraint: $1\le {\mathbf{ns}}\le {\mathbf{n}}$.
On entry, ${\mathbf{ns}}=⟨\mathit{\text{value}}⟩$ and ${\mathbf{ne}}=⟨\mathit{\text{value}}⟩$.
Constraint: ${\mathbf{ns}}\ne {\mathbf{ne}}$.
${\mathbf{ifail}}=2$
On entry, ${\mathbf{nnz}}=⟨\mathit{\text{value}}⟩$ and ${\mathbf{n}}=⟨\mathit{\text{value}}⟩$.
Constraint: if ${\mathbf{direct}}=\mathrm{.FALSE.}$, $1\le {\mathbf{nnz}}\le {\mathbf{n}}×\left({\mathbf{n}}-1\right)/2$.
On entry, ${\mathbf{nnz}}=⟨\mathit{\text{value}}⟩$ and ${\mathbf{n}}=⟨\mathit{\text{value}}⟩$.
Constraint: if ${\mathbf{direct}}=\mathrm{.TRUE.}$, $1\le {\mathbf{nnz}}\le {\mathbf{n}}×\left({\mathbf{n}}-1\right)$.
${\mathbf{ifail}}=3$
On entry, $k=⟨\mathit{\text{value}}⟩$, ${\mathbf{irow}}\left(k\right)=⟨\mathit{\text{value}}⟩$, ${\mathbf{icol}}\left(k\right)=⟨\mathit{\text{value}}⟩$ and ${\mathbf{n}}=⟨\mathit{\text{value}}⟩$.
Constraint: $1\le {\mathbf{irow}}\left(k\right)\le {\mathbf{n}}$, $1\le {\mathbf{icol}}\left(k\right)\le {\mathbf{n}}$; ${\mathbf{icol}}\left(k\right)\ne {\mathbf{irow}}\left(k\right)$ when ${\mathbf{direct}}=\mathrm{.TRUE.}$.
${\mathbf{ifail}}=4$
On entry, $k=⟨\mathit{\text{value}}⟩$, ${\mathbf{irow}}\left(k\right)=⟨\mathit{\text{value}}⟩$, ${\mathbf{icol}}\left(k\right)=⟨\mathit{\text{value}}⟩$ and ${\mathbf{n}}=⟨\mathit{\text{value}}⟩$.
Constraint: $1\le {\mathbf{irow}}\left(k\right)<{\mathbf{icol}}\left(k\right)\le {\mathbf{n}}$ when ${\mathbf{direct}}=\mathrm{.FALSE.}$.
${\mathbf{ifail}}=5$
On entry, $k=⟨\mathit{\text{value}}⟩$, ${\mathbf{d}}\left(k\right)=⟨\mathit{\text{value}}⟩$.
Constraint: ${\mathbf{d}}\left(k\right)>0.0$.
${\mathbf{ifail}}=6$
On entry, $k=⟨\mathit{\text{value}}⟩$, ${\mathbf{irow}}\left(k\right)=⟨\mathit{\text{value}}⟩$, ${\mathbf{irow}}\left(k-1\right)=⟨\mathit{\text{value}}⟩$, ${\mathbf{icol}}\left(k\right)=⟨\mathit{\text{value}}⟩$, ${\mathbf{icol}}\left(k-1\right)=⟨\mathit{\text{value}}⟩$.
Constraints: ${\mathbf{irow}}\left(k-1\right)<{\mathbf{irow}}\left(k\right)$ or ${\mathbf{irow}}\left(k-1\right)={\mathbf{irow}}\left(k\right)$ and ${\mathbf{icol}}\left(k-1\right)<{\mathbf{icol}}\left(k\right)$.
${\mathbf{ifail}}=7$
On entry, $k=⟨\mathit{\text{value}}⟩$ ${\mathbf{irow}}\left(k\right)=⟨\mathit{\text{value}}⟩$, ${\mathbf{irow}}\left(k-1\right)=⟨\mathit{\text{value}}⟩$ ${\mathbf{icol}}\left(k\right)=⟨\mathit{\text{value}}⟩$, ${\mathbf{icol}}\left(k-1\right)=⟨\mathit{\text{value}}⟩$.
Constraint: ${\mathbf{irow}}\left(k\right)\ne {\mathbf{irow}}\left(k-1\right)$ or ${\mathbf{icol}}\left(k\right)\ne {\mathbf{icol}}\left(k-1\right)$.
${\mathbf{ifail}}=8$
On entry, ${\mathbf{ns}}=⟨\mathit{\text{value}}⟩$ and ${\mathbf{ne}}=⟨\mathit{\text{value}}⟩$.
No connected network exists between vertices ns and ne.
${\mathbf{ifail}}=-99$
See Section 7 in the Introduction to the NAG Library FL Interface for further information.
${\mathbf{ifail}}=-399$
Your licence key may have expired or may not have been installed correctly.
See Section 8 in the Introduction to the NAG Library FL Interface for further information.
${\mathbf{ifail}}=-999$
Dynamic memory allocation failed.
See Section 9 in the Introduction to the NAG Library FL Interface for further information.

7Accuracy

The results are exact, except for the obvious rounding errors in summing the distances in the length of the shortest path.

8Parallelism and Performance

h03adf is based upon Dijkstra's algorithm (see Dijkstra (1959)), which attempts to find a path ${n}_{s}\to {n}_{e}$ between two specified vertices ${n}_{s}$ and ${n}_{e}$ of shortest length $d\left({n}_{s},{n}_{e}\right)$.
The algorithm proceeds by assigning labels to each vertex, which may be temporary or permanent. A temporary label can be changed, whereas a permanent one cannot. For example, if vertex $p$ has a permanent label $\left(q,r\right)$, then $r$ is the distance $d\left({n}_{s},r\right)$ and $q$ is the previous vertex on a shortest length ${n}_{s}\to p$ path. If the label is temporary, then it has the same meaning but it refers only to the shortest ${n}_{s}\to p$ path found so far. A shorter one may be found later, in which case the label may become permanent.
The algorithm consists of the following steps.
1. 1.Assign the permanent label $\left(-,0\right)$ to vertex ${n}_{s}$ and temporary labels $\left(-,\infty \right)$ to every other vertex. Set $k={n}_{s}$ and go to 2.
2. 2.Consider each vertex $y$ adjacent to vertex $k$ with a temporary label in turn. Let the label at $k$ be $\left(p,q\right)$ and at $y\left(r,s\right)$. If $q+{d}_{ky}, then a new temporary label $\left(k,q+{d}_{ky}\right)$ is assigned to vertex $y$; otherwise no change is made in the label of $y$. When all vertices $y$ with temporary labels adjacent to $k$ have been considered, go to 3.
3. 3.From the set of temporary labels, select the one with the smallest second component and declare that label to be permanent. The vertex it is attached to becomes the new vertex $k$. If $k={n}_{e}$ go to 4. Otherwise go to 2 unless no new vertex can be found (e.g., when the set of temporary labels is ‘empty’ but $k\ne {n}_{e}$, in which case no connected network exists between vertices ${n}_{s}$ and ${n}_{e}$).
4. 4.To find the shortest path, let $\left(y,z\right)$ denote the label of vertex ${n}_{e}$. The column label ($z$) gives $d\left({n}_{s},{n}_{e}\right)$ while the row label ($y$) then links back to the previous vertex on a shortest length ${n}_{s}\to {n}_{e}$ path. Go to vertex $y$. Suppose that the (permanent) label of vertex $y$ is $\left(w,x\right)$, then the next previous vertex is $w$ on a shortest length ${n}_{s}\to y$ path. This process continues until vertex ${n}_{s}$ is reached. Hence the shortest path is
 $ns→⋯→w→y→ne,$
which has length $d\left({n}_{s},{n}_{e}\right)$.

10Example

This example finds the shortest path between vertices $1$ and $11$ for the undirected network