nag_mip_shortestpath (h03ad) 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 \leftrightarrow 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

d

, in which the element

d_{i j}

gives the length of the arc

i \to j

;

d_{i j} = 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 = (\begin{matrix} 0 & d_{12} & d_{13} & d_{14} \\ d_{21} & 0 & d_{23} & d_{24} \\ d_{31} & d_{32} & 0 & d_{34} \\ d_{41} & d_{42} & d_{43} & 0 \end{matrix}) .

If the network is undirected,

d

is symmetric since

d_{i j} = d_{j i}

(i.e., the length of the arc

i \to j \equiv

the length of the arc

j \to i

The method used by nag_mip_shortestpath (h03ad) is described in detail in Further Comments.

References

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

Parameters

Compulsory Input Parameters

1: $n$ – int64int32nag_int scalar

n

, the number of vertices.

Constraint:

n \geq 2

2: $ns$ – int64int32nag_int scalar

3: $ne$ – int64int32nag_int scalar

n_{s}

and

n_{e}

, the labels of the first and last vertices, respectively, between which the shortest path is sought.

Constraints:

$1 \leq ns \leq n$ ;
$1 \leq ne \leq n$ ;
$ns \neq ne$ .

4: $direct$ – logical scalar

Indicates whether the network is directed or undirected.

$direct = true$: The network is directed.
$direct = false$: The network is undirected.

5: $d (nz)$ – double array

The nonzero elements of the distance matrix

D

, ordered by increasing row index and increasing column index within each row. More precisely,

d (k)

must contain the value of the nonzero element with indices (

irow (k), icol (k)

); this is the length of the arc from the vertex with label

irow (k)

to the vertex with label

icol (k)

. Elements with the same row and column indices are not allowed. If

direct = false

, then only those nonzero elements in the strict upper triangle of

d

need be supplied since

d_{i j} = d_{j i}

. (nag_sparse_real_gen_sort (f11za) may be used to sort the elements of an arbitrarily ordered matrix into the required form. This is illustrated in Example.)

Constraint:

d (k) > 0.0

, for

k = 1, 2, \dots, nz

6: $irow (nz)$ – int64int32nag_int array

7: $icol (nz)$ – int64int32nag_int array

irow (k)

and

icol (k)

must contain the row and column indices, respectively, for the nonzero element stored in

d (k)

Constraints:

irow and icol must satisfy the following constraints (which may be imposed by a call to nag_sparse_real_gen_sort (f11za)):

$irow (k - 1) < irow (k)$ ;
$irow (k - 1) = irow (k)$ and $icol (k - 1) < icol (k)$ , for $k = 2, 3, \dots, nz$ .

In addition, if

direct = true

1 \leq irow (k) \leq n

1 \leq icol (k) \leq n

and

irow (k) \neq icol (k)

;

if $direct = false$ , $1 \leq irow (k) < icol (k) \leq n$ .

Optional Input Parameters

1: $nz$ – int64int32nag_int scalar

Default: the dimension of the arrays irow, icol, d. (An error is raised if these dimensions are not equal.)

The number of nonzero elements in the distance matrix

D

Constraints:

if $direct = true$ , $1 \leq nz \leq n \times (n - 1)$ ;
if $direct = false$ , $1 \leq nz \leq n \times (n - 1) / 2$ .

Output Parameters

1: $splen$ – double scalar: The length of the shortest path between the specified vertices $n_{s}$ and $n_{e}$ .
2: $path (n)$ – int64int32nag_int array: Contains details of the shortest path between the specified vertices $n_{s}$ and $n_{e}$ . More precisely, $ns = path (1) \to path (2) \to \dots \to path (p) = ne$ for some $p \leq n$ . The remaining $(n - p)$ elements are set to zero.
3: $ifail$ – int64int32nag_int scalar: $ifail = 0$ unless the function detects an error (see Error Indicators and Warnings).

Error Indicators and Warnings

Errors or warnings detected by the function:

$ifail = 1$

On entry,	$n < 2$ ,
or	$ns < 1$ ,
or	$ns > n$ ,
or	$ne < 1$ ,
or	$ne > n$ ,
or	$ns = ne$ .

$ifail = 2$

On entry,	$nz > n \times (n - 1)$ when $direct = true$ ,
or	$nz > n \times (n - 1) / 2$ when $direct = false$ ,
or	$nz < 1$ .

$ifail = 3$: On entry, $irow (k) < 1$ or $irow (k) > n$ or $icol (k) < 1$ or $icol (k) > n$ or $irow (k) = icol (k)$ for some $k$ when $direct = true$ .

$ifail = 4$: On entry, $irow (k) < 1$ or $irow (k) \geq icol (k)$ or $icol (k) > n$ for some $k$ when $direct = false$ .

$ifail = 5$: $d (k) \leq 0.0$ for some $k$ .

$ifail = 6$: On entry, $irow (k - 1) > irow (k)$ or $irow (k - 1) = irow (k)$ and $icol (k - 1) > icol (k)$ for some $k$ .

$ifail = 7$: On entry, $irow (k - 1) = irow (k)$ and $icol (k - 1) = icol (k)$ for some $k$ .

$ifail = 8$: No connected network exists between vertices ns and ne.

$ifail = - 99$: An unexpected error has been triggered by this routine. Please contact NAG.

$ifail = - 399$: Your licence key may have expired or may not have been installed correctly.

$ifail = - 999$: Dynamic memory allocation failed.

Accuracy

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

Further Comments

nag_mip_shortestpath (h03ad) 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 (n_{s}, n_{e})

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

(q, r)

, then

r

is the distance

d (n_{s}, r)

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.

Assign the permanent label

(-, 0)

to vertex

n_{s}

and temporary labels

(-, \infty)

to every other vertex. Set

k = n_{s}

and go to 2.

Consider each vertex

y

adjacent to vertex

k

with a temporary label in turn. Let the label at

k

(p, q)

and at

y (r, s)

. If

q + d_{k y} < s

, then a new temporary label

(k, q + d_{k y})

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.

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 \neq n_{e}

, in which case no connected network exists between vertices

n_{s}

and

n_{e}

To find the shortest path, let

(y, z)

denote the label of vertex

n_{e}

. The column label (

z

) gives

d (n_{s}, n_{e})

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

(w, x)

, 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

n_{s} \to \dots \to w \to y \to n_{e},

which has length

d (n_{s}, n_{e})

Example

This example finds the shortest path between vertices

1

and

11

for the undirected network

Open in the MATLAB editor: h03ad_example

function h03ad_example


fprintf('h03ad example results\n\n');

n  = int64(11);
ns = int64(1);
ne = n;
direct = false;
d = [  5;   6;   5;
            2;        4;
                 1;        4;
                           1;   3;
                           1;             9;
                                1;   6;        7;
                                          8;
                                          1;        4;
                                               2;   2;
                                                    4];
irow = [int64(1);1;1;  2;2;  3;3;  4;4;  5;5;  6;6; 6;  7; 8; 8;   9; 9; 10];
icol = [int64(2);3;4;  3;5;  4;6;  6;7;  6;9;  7;8;10;  9; 9;11;  10;11; 11];

[splen, path, ifail] = h03ad(n, ns, ne, direct, d, irow, icol);

fprintf('Shortest path = ');
j = 1;
while path(j)~=0;
  if j>1
    fprintf('  to  ');
  end
  fprintf('%2d', path(j));
  j = j+1;
end
fprintf('\n\nLength of shortest path = %16.6g\n', splen);

h03ad example results

Shortest path =  1  to   4  to   6  to   8  to   9  to  11

Length of shortest path =               15

PDF version (NAG web site, 64-bit version, 64-bit version)

Chapter Contents

Chapter Introduction

NAG Toolbox