\input cwebmac
% This file is part of the Stanford GraphBase (c) Stanford University 1993
% This material goes at the beginning of all Stanford GraphBase CWEB files

\def\topofcontents{
  \leftline{\sc\today\ at \hours}\bigskip\bigskip
  \centerline{\titlefont\title}}

\font\ninett=cmtt9
\def\botofcontents{\vskip 0pt plus 1filll
    \ninerm\baselineskip10pt
    \noindent\copyright\ 1993 Stanford University
    \bigskip\noindent
    This file may be freely copied and distributed, provided that
    no changes whatsoever are made. All users are asked to help keep
    the Stanford GraphBase files consistent and ``uncorrupted,''
    identical everywhere in the world. Changes are permissible only
    if the modified file is given a new name, different from the names of
    existing files in the Stanford GraphBase, and only if the modified file is
    clearly identified as not being part of that GraphBase.
    (The {\ninett CWEB} system has a ``change file'' facility by
    which users can easily make minor alterations without modifying
    the master source files in any way. Everybody is supposed to use
    change files instead of changing the files.)
    The author has tried his best to produce correct and useful programs,
    in order to help promote computer science research,
    but no warranty of any kind should be assumed.
    \smallskip\noindent
    Preliminary work on the Stanford GraphBase project
    was supported in part by National Science
    Foundation grant CCR-86-10181.}

\def\prerequisite#1{\def\startsection{\noindent
    Important: Before reading {\sc\title},
    please read or at least skim the program for {\sc#1}.\bigskip
    \let\startsection=\stsec\stsec}}
\def\prerequisites#1#2{\def\startsection{\noindent
    Important: Before reading {\sc\title}, please read
    or at least skim the programs for {\sc#1} and {\sc#2}.\bigskip
    \let\startsection=\stsec\stsec}}



\def\title{GB\_\,DIJK}

\prerequisite{GB\_\,GRAPH}

\N{1}{1}Introduction. The GraphBase demonstration routine $\\{dijkstra}(\\{uu},%
\\{vv},\\{gg},\\{hh})$
finds a shortest path from vertex~\\{uu} to vertex~\\{vv} in graph~\\{gg}, with
the
aid of an optional heuristic function~\\{hh}. This function implements a
version of Dijkstra's algorithm, a general procedure for determining
shortest paths in a directed graph that has nonnegative arc lengths
[E.~W. Dijkstra, ``A note on two problems in connexion with graphs,''
{\sl Numerische Mathematik\/ \bf1} (1959), 269--271].

If \\{hh} is null, the length of
every arc in \\{gg} must be nonnegative. If \\{hh} is non-null, \\{hh} should
be
a function defined on the vertices of the graph such that the
length \|d of an arc from \|u to~\|v always satisfies the condition
$$ d \ge \\{hh}(u)-\\{hh}(v)\,. $$
In such a case, we can effectively replace each arc length \|d by
$\|d-\\{hh}(\|u)+\\{hh}(\|v)$, obtaining a graph with nonnegative arc lengths.
The shortest paths between vertices in this modified graph
are the same as they were in the original graph.

The basic idea of Dijkstra's algorithm is to explore the vertices of
the graph in order of their distance from the starting vertex~\\{uu},
proceeding until \\{vv} is encountered. If the distances have been
modified by a heuristic function \\{hh} such that \\{hh}(\|u) happens to equal
the true distance from \|u to~\\{vv}, for all~\|u,
then all of the modified distances on
shortest paths to \\{vv} will be zero. This means that the algorithm
will explore all of the most useful arcs first, without
wandering off in unfruitful directions. In practice we usually
don't know the exact distances to \\{vv} in advance, but we can often
compute an approximate value \\{hh}(\|u) that will help focus the search.

If the external variable \\{verbose} is nonzero, \\{dijkstra} will record
its activities on the standard output file by printing the distances
from \\{uu} to all vertices it visits.

After \\{dijkstra} has found a shortest path, it returns the length of
that path. If no path from \\{uu} to~\\{vv} exists (in particular, if
\\{vv} is~$\NULL$), it returns ${-}\T{1}$; in such a case, the shortest
distances from
\\{uu} to all vertices reachable from~\\{uu} will have been computed and
stored in the graph.
An auxiliary function, \\{print\_dijkstra\_result}(\\{vv}), can be used
to display the actual path found, if one exists.

Examples of the use of \\{dijkstra} appear in the {\sc LADDERS}
demonstration module.

\fi

\M{2}This \CEE/ module is meant to be loaded as part of another program.
It has the following simple structure:

\Y\B\8\#\&{include} \.{"gb\_graph.h"}\C{ define the standard GraphBase data
structures }\6
\ATH\7
\X16:Priority queue procedures\X\6
\X8:Global declarations\X\6
\X9:The \\{dijkstra} procedure\X\6
\X14:The \\{print\_dijkstra\_result} procedure\X\par
\fi

\M{3}Users of {\sc GB\_\,DIJK} should include the header file \.{gb\_dijk.h}:

\Y\B\4\X3:\.{gb\_dijk.h }\X${}\E{}$\6
\&{extern} \&{long} \\{dijkstra}(\,);\C{ procedure to calculate shortest paths
}\6
\8\#\&{define} \\{print\_dijkstra\_result} \5\\{p\_dijkstra\_result}\C{
shorthand for linker }\6
\&{extern} \&{void} \\{print\_dijkstra\_result}(\,);\C{ procedure to display
the answer }\par
\As5, 6, 7\ETs25.\fi

\N{1}{4}The main algorithm.
As Dijkstra's algorithm proceeds, it ``knows'' shortest paths from \\{uu}
to more and more vertices; we will call these vertices ``known.''
Initially only \\{uu} itself is known. The procedure terminates when \\{vv}
becomes known, or when all vertices reachable from~\\{uu} are known.

Dijkstra's algorithm looks at all vertices adjacent to known vertices.
A vertex is said to have been ``seen'' if it is either known or
adjacent to a vertex that's known.

The algorithm proceeds by learning to know all vertices in a greater
and greater radius from the starting point. Thus, if \|v~is a known
vertex at distance~\|d from~\\{uu}, every vertex at distance less than~\|d from
\\{uu} will also be known.  (Throughout this discussion the word
``distance'' actually means ``distance modified by the heuristic
function''; we omit mentioning the heuristic because we can assume that
the algorithm is operating on a graph with modified distances.)

The algorithm maintains an auxiliary list of all vertices that have been
seen but aren't yet known. For every such vertex~\|v, it remembers
the shortest distance~\|d from \\{uu} to~\|v by a path that passes entirely
through known vertices except for the very last arc.

This auxiliary list is actually a priority queue, ordered by the \|d values.
If \|v~is a vertex of the priority queue having the smallest \|d, we can
remove \|v from the queue and consider it known, because there cannot be
a path of length less than~\|d from \\{uu} to~\|v. (This is where the
assumption of nonnegative arc length is crucial to the algorithm's validity.)

\fi

\M{5}To implement the ideas just sketched, we use several of the utility
fields in vertex records. Each vertex~\|v has a \\{dist} field $\|v\MG%
\\{dist}$,
which represents its true distance from \\{uu} if \|v is known; otherwise
$\|v\MG\\{dist}$ represents the shortest distance from \\{uu} discovered so
far.

Each vertex \|v also has a \\{backlink} field $\|v\MG\\{backlink}$, which is
non-$\NULL$
if and only if \|v has been seen. In that case $\|v\MG\\{backlink}$ is a vertex
one
step ``closer'' to \\{uu}, on a path from \\{uu} to \|v that achieves the
current distance $\|v\MG\\{dist}$. (Exception:
Vertex~\\{uu} has a backlink pointing to itself.) The backlink
fields thereby allow us to construct shortest paths from \\{uu} to all the
known vertices, if desired.

\Y\B\4\D$\\{dist}$ \5
$\|z.{}$\|I\C{ distance from \\{uu}, modified by \\{hh},
appears in vertex utility field \|z }\par
\B\4\D$\\{backlink}$ \5
$\|y.{}$\|V\C{ pointer to previous vertex appears in utility field \|y }\par
\Y\B\4\X3:\.{gb\_dijk.h }\X${}\mathrel+\E{}$\6
\8\#\&{define} \\{dist} \5${}\|z.\|I{}$\6
\8\#\&{define} \\{backlink} \5${}\|y.\|V{}$\par
\fi

\M{6}The priority queue is implemented by four procedures:

\begingroup
\def\]#1 {\smallskip\hangindent2\parindent \hangafter1 \indent #1 }

\]\\{init\_queue}(\|d) makes the queue empty and prepares for subsequent keys $%
\G$ \|d.

\]$\\{enqueue}(\|v,\|d)$ puts vertex \|v in the queue and assigns it the key
value $\|v\MG\\{dist}\K\|d$.

\]$\\{requeue}(\|v,\|d)$ takes vertex \|v out of the queue and enters it again
with the smaller key value $\|v\MG\\{dist}\K\|d$.

\]\\{del\_min}(\,) removes a vertex with minimum key from the queue and
returns a pointer to that vertex. If the queue is empty, $\NULL$ is returned.

\endgroup\smallskip\noindent
These procedures are accessed via external pointers, so that the user
of {\sc GB\_\,DIJK} can supply alternate queueing methods if desired.

\Y\B\4\X3:\.{gb\_dijk.h }\X${}\mathrel+\E{}$\6
\&{extern} \&{void} ${}({*}\\{init\_queue})(\,){}$;\C{ create an empty priority
queue for \\{dijkstra} }\6
\&{extern} \&{void} ${}({*}\\{enqueue})(\,){}$;\C{ insert a new element in the
priority queue }\6
\&{extern} \&{void} ${}({*}\\{requeue})(\,){}$;\C{ decrease the key of an
element in the queue }\6
\&{extern} \&{Vertex} ${}{*}({*}\\{del\_min})(\,){}$;\C{ remove an element with
smallest key }\par
\fi

\M{7}The heuristic function might take a while to compute, so we avoid
recomputation by storing \\{hh}(\|v) in another utility field $\|v\MG\\{hh%
\_val}$
once we've evaluated it.

\Y\B\4\D$\\{hh\_val}$ \5
$\|x.{}$\|I\C{ computed value of \\{hh}(\|v) }\par
\Y\B\4\X3:\.{gb\_dijk.h }\X${}\mathrel+\E{}$\6
\8\#\&{define} \\{hh\_val} \5${}\|x.\|I{}$\par
\fi

\M{8}If no heuristic function is supplied by the user, we replace it by a
dummy function that simply returns 0 in all cases.

\Y\B\4\X8:Global declarations\X${}\E{}$\6
\&{long} \\{dummy}(\|v)\1\1\6
\&{Vertex} ${}{*}\|v;\2\2{}$\6
${}\{{}$\5
\1\&{return} \T{0};\5
${}\}{}$\2\par
\A15.
\U2.\fi

\M{9}Here now is \\{dijkstra}:

\Y\B\4\X9:The \\{dijkstra} procedure\X${}\E{}$\6
\&{long} ${}\\{dijkstra}(\\{uu},\39\\{vv},\39\\{gg},\39\\{hh}){}$\1\1\6
\&{Vertex} ${}{*}\\{uu}{}$;\C{ the starting point }\6
\&{Vertex} ${}{*}\\{vv}{}$;\C{ the ending point }\6
\&{Graph} ${}{*}\\{gg}{}$;\C{ the graph they belong to }\6
\&{long} ${}({*}\\{hh})(\,){}$;\C{ heuristic function }\2\2\6
${}\{{}$\5
\1\&{register} \&{Vertex} ${}{*}\|t{}$;\C{ current vertex of interest }\7
\&{if} ${}(\R\\{hh}){}$\1\5
${}\\{hh}\K\\{dummy}{}$;\C{ change to default heuristic }\2\6
\X10:Make \\{uu} the only vertex seen; also make it known\X;\6
${}\|t\K\\{uu};{}$\6
\&{if} (\\{verbose})\1\5
\X12:Print initial message\X;\2\6
\&{while} ${}(\|t\I\\{vv}){}$\5
${}\{{}$\1\6
\X11:Put all unseen vertices adjacent to \|t into the queue, and update the
distances of other vertices adjacent to~\|t\X;\6
${}\|t\K({*}\\{del\_min})(\,);{}$\6
\&{if} ${}(\|t\E\NULL){}$\1\5
\&{return} ${}{-}\T{1}{}$;\C{ if the queue becomes empty,
there's no way to get to \\{vv} }\2\6
\&{if} (\\{verbose})\1\5
\X13:Print the distance to \|t\X;\2\6
\4${}\}{}$\2\6
\&{return} \\{vv}${}\MG\\{dist}-\\{vv}\MG\\{hh\_val}+\\{uu}\MG\\{hh\_val}{}$;%
\C{ true distance from \\{uu} to \\{vv} }\6
\4${}\}{}$\2\par
\U2.\fi

\M{10}As stated above, a vertex is considered seen only when its backlink
isn't null, and known only when it is seen but not in the queue.

\Y\B\4\X10:Make \\{uu} the only vertex seen; also make it known\X${}\E{}$\6
\&{for} ${}(\|t\K\\{gg}\MG\\{vertices}+\\{gg}\MG\|n-\T{1};{}$ ${}\|t\G\\{gg}\MG%
\\{vertices};{}$ ${}\|t\MM){}$\1\5
${}\|t\MG\\{backlink}\K\NULL;{}$\2\6
${}\\{uu}\MG\\{backlink}\K\\{uu};{}$\6
${}\\{uu}\MG\\{dist}\K\T{0};{}$\6
${}\\{uu}\MG\\{hh\_val}\K({*}\\{hh})(\\{uu});{}$\6
${}({*}\\{init\_queue})(\T{0\$L}){}$;\C{ make the priority queue empty }\par
\U9.\fi

\M{11}Here we help the \CEE/ compiler in case it hasn't got a great optimizer.

\Y\B\4\X11:Put all unseen vertices adjacent to \|t into the queue, and update
the distances of other vertices adjacent to~\|t\X${}\E{}$\6
${}\{{}$\5
\1\&{register} \&{Arc} ${}{*}\|a{}$;\C{ an arc leading from \|t }\6
\&{register} \&{long} \|d${}\K\|t\MG\\{dist}-\|t\MG\\{hh\_val};{}$\7
\&{for} ${}(\|a\K\|t\MG\\{arcs};{}$ \|a; ${}\|a\K\|a\MG\\{next}){}$\5
${}\{{}$\1\6
\&{register} \&{Vertex} ${}{*}\|v\K\|a\MG\\{tip}{}$;\C{ a vertex adjacent to %
\|t }\7
\&{if} ${}(\|v\MG\\{backlink}){}$\5
${}\{{}$\C{ \|v has already been seen }\1\6
\&{register} \&{long} \\{dd}${}\K\|d+\|a\MG\\{len}+\|v\MG\\{hh\_val};{}$\7
\&{if} ${}(\\{dd}<\|v\MG\\{dist}){}$\5
${}\{{}$\1\6
${}\|v\MG\\{backlink}\K\|t;{}$\6
${}({*}\\{requeue})(\|v,\39\\{dd}){}$;\C{ we found a better way to get there }\6
\4${}\}{}$\2\6
\4${}\}{}$\5
\2\&{else}\5
${}\{{}$\C{ \|v hasn't been seen before }\1\6
${}\|v\MG\\{hh\_val}\K({*}\\{hh})(\|v);{}$\6
${}\|v\MG\\{backlink}\K\|t;{}$\6
${}({*}\\{enqueue})(\|v,\39\|d+\|a\MG\\{len}+\|v\MG\\{hh\_val});{}$\6
\4${}\}{}$\2\6
\4${}\}{}$\2\6
\4${}\}{}$\2\par
\U9.\fi

\M{12}The \\{dist} fields don't contain true distances in the graph; they
represent distances modified by the heuristic function. The true distance
from \\{uu} to vertex \|v is $\|v\MG\\{dist}-\|v\MG\\{hh\_val}+\\{uu}\MG\\{hh%
\_val}$.

When printing the results, we show true distances. Also, if a nontrivial
heuristic is being used, we give the \\{hh} value in brackets; the user can
then
observe that vertices are becoming known in order of true distance
plus \\{hh} value.

\Y\B\4\X12:Print initial message\X${}\E{}$\6
${}\{{}$\5
\1${}\\{printf}(\.{"Distances\ from\ \%s"},\39\\{uu}\MG\\{name});{}$\6
\&{if} ${}(\\{hh}\I\\{dummy}){}$\1\5
${}\\{printf}(\.{"\ [\%ld]"},\39\\{uu}\MG\\{hh\_val});{}$\2\6
\\{printf}(\.{":\\n"});\6
\4${}\}{}$\2\par
\U9.\fi

\M{13}\B\X13:Print the distance to \|t\X${}\E{}$\6
${}\{{}$\5
\1${}\\{printf}(\.{"\ \%ld\ to\ \%s"},\39\|t\MG\\{dist}-\|t\MG\\{hh\_val}+%
\\{uu}\MG\\{hh\_val},\39\|t\MG\\{name});{}$\6
\&{if} ${}(\\{hh}\I\\{dummy}){}$\1\5
${}\\{printf}(\.{"\ [\%ld]"},\39\|t\MG\\{hh\_val});{}$\2\6
${}\\{printf}(\.{"\ via\ \%s\\n"},\39\|t\MG\\{backlink}\MG\\{name});{}$\6
\4${}\}{}$\2\par
\U9.\fi

\M{14}After \\{dijkstra} has found a shortest path, the backlinks from~\\{vv}
specify the steps of that path. We want to print the path in the forward
direction, so we reverse the links.

We also unreverse them again, just in case the user didn't want the backlinks
to be trashed. Indeed, this procedure can be used for any vertex \\{vv} whose
backlink is non-null, not only the \\{vv} that was a parameter to \\{dijkstra}.

List reversal is conveniently regarded as a process of popping off one stack
and pushing onto another.

\Y\B\4\D$\\{print\_dijkstra\_result}$ \5
\\{p\_dijkstra\_result}\C{ shorthand for linker }\par
\Y\B\4\X14:The \\{print\_dijkstra\_result} procedure\X${}\E{}$\6
\&{void} \\{print\_dijkstra\_result}(\\{vv})\1\1\6
\&{Vertex} ${}{*}\\{vv}{}$;\C{ ending vertex }\2\2\6
${}\{{}$\5
\1\&{register} \&{Vertex} ${}{*}\|t,{}$ ${}{*}\|p,{}$ ${}{*}\|q{}$;\C{
registers for reversing links }\7
${}\|t\K\NULL,\39\|p\K\\{vv};{}$\6
\&{if} ${}(\R\|p\MG\\{backlink}){}$\5
${}\{{}$\1\6
${}\\{printf}(\.{"Sorry,\ \%s\ is\ unreac}\)\.{hable.\\n"},\39\|p\MG%
\\{name});{}$\6
\&{return};\6
\4${}\}{}$\2\6
\&{do}\5
${}\{{}$\C{ pop an item from \|p to \|t }\1\6
${}\|q\K\|p\MG\\{backlink};{}$\6
${}\|p\MG\\{backlink}\K\|t;{}$\6
${}\|t\K\|p;{}$\6
${}\|p\K\|q;{}$\6
\4${}\}{}$\5
\2\5
\&{while} ${}(\|t\I\|p){}$;\C{ the loop stops with $\|t\E\|p\E\\{uu}$ }\6
\&{do}\5
${}\{{}$\1\6
${}\\{printf}(\.{"\%10ld\ \%s\\n"},\39\|t\MG\\{dist}-\|t\MG\\{hh\_val}+\|p\MG%
\\{hh\_val},\39\|t\MG\\{name});{}$\6
${}\|t\K\|t\MG\\{backlink};{}$\6
\4${}\}{}$\5
\2\5
\&{while} (\|t);\6
${}\|t\K\|p;{}$\6
\&{do}\5
${}\{{}$\C{ pop an item from \|t to \|p }\1\6
${}\|q\K\|t\MG\\{backlink};{}$\6
${}\|t\MG\\{backlink}\K\|p;{}$\6
${}\|p\K\|t;{}$\6
${}\|t\K\|q;{}$\6
\4${}\}{}$\5
\2\5
\&{while} ${}(\|p\I\\{vv});{}$\6
\4${}\}{}$\2\par
\U2.\fi

\N{1}{15}Priority queues. Here we provide a simple doubly linked list
for queueing; this is a convenient default, good enough for applications
that aren't too large. (See {\sc MILES\_\,SPAN} for implementations of
other schemes that are more efficient when the queue gets large.)

The two queue links occupy two of a vertex's remaining utility fields.

\Y\B\4\D$\\{llink}$ \5
$\|v.{}$\|V\C{ \\{llink} is stored in utility field \|v of a vertex }\par
\B\4\D$\\{rlink}$ \5
$\|w.{}$\|V\C{ \\{rlink} is stored in utility field \|w of a vertex }\par
\Y\B\4\X8:Global declarations\X${}\mathrel+\E{}$\6
\&{void} ${}({*}\\{init\_queue})(\,)\K\\{init\_dlist}{}$;\C{ create an empty
dlist }\6
\&{void} ${}({*}\\{enqueue})(\,)\K\\{enlist}{}$;\C{ insert a new element in
dlist }\6
\&{void} ${}({*}\\{requeue})(\,)\K\\{reenlist}{}$;\C{ decrease the key of an
element in dlist }\6
\&{Vertex} ${}{*}({*}\\{del\_min})(\,)\K\\{del\_first}{}$;\C{ remove element
with smallest key }\par
\fi

\M{16}There's a special list head, from which we get to everything else in the
queue in decreasing order of keys by following \\{llink} fields.

The following declaration actually provides for 128 list heads. Only the first
of these is used here, but we'll find something to do with the
other 127 later.

\Y\B\4\X16:Priority queue procedures\X${}\E{}$\6
\&{Vertex} \\{head}[\T{128}];\C{ list-head elements that are always present }\7
\&{void} \\{init\_dlist}(\|d)\1\1\6
\&{long} \|d;\2\2\6
${}\{{}$\1\6
${}\\{head}\MG\\{llink}\K\\{head}\MG\\{rlink}\K\\{head};{}$\6
${}\\{head}\MG\\{dist}\K\|d-\T{1}{}$;\C{ a value guaranteed to be smaller than
any actual key }\6
\4${}\}{}$\2\par
\As17, 18, 19, 21, 22, 23\ETs24.
\U2.\fi

\M{17}It seems reasonable to assume that an element entering the queue for the
first time will tend to have a larger key than the other elements.

Indeed, in the special case that all arcs in the graph have the same
length, this strategy turns out to be quite fast. For in that case,
every vertex is added to the end of the queue and deleted from the
front, without any requeueing; the algorithm produces a strict
first-in-first-out queueing discipline and performs a breadth-first search.

\Y\B\4\X16:Priority queue procedures\X${}\mathrel+\E{}$\6
\&{void} ${}\\{enlist}(\|v,\39\|d){}$\1\1\6
\&{Vertex} ${}{*}\|v;{}$\6
\&{long} \|d;\2\2\6
${}\{{}$\5
\1\&{register} \&{Vertex} ${}{*}\|t\K\\{head}\MG\\{llink};{}$\7
${}\|v\MG\\{dist}\K\|d;{}$\6
\&{while} ${}(\|d<\|t\MG\\{dist}){}$\1\5
${}\|t\K\|t\MG\\{llink};{}$\2\6
${}\|v\MG\\{llink}\K\|t;{}$\6
${}(\|v\MG\\{rlink}\K\|t\MG\\{rlink})\MG\\{llink}\K\|v;{}$\6
${}\|t\MG\\{rlink}\K\|v;{}$\6
\4${}\}{}$\2\par
\fi

\M{18}\B\X16:Priority queue procedures\X${}\mathrel+\E{}$\6
\&{void} ${}\\{reenlist}(\|v,\39\|d){}$\1\1\6
\&{Vertex} ${}{*}\|v;{}$\6
\&{long} \|d;\2\2\6
${}\{{}$\5
\1\&{register} \&{Vertex} ${}{*}\|t\K\|v\MG\\{llink};{}$\7
${}(\|t\MG\\{rlink}\K\|v\MG\\{rlink})\MG\\{llink}\K\|v\MG\\{llink}{}$;\C{
remove \|v }\6
${}\|v\MG\\{dist}\K\|d{}$;\C{ we assume that the new \\{dist} is smaller than
it was before }\6
\&{while} ${}(\|d<\|t\MG\\{dist}){}$\1\5
${}\|t\K\|t\MG\\{llink};{}$\2\6
${}\|v\MG\\{llink}\K\|t;{}$\6
${}(\|v\MG\\{rlink}\K\|t\MG\\{rlink})\MG\\{llink}\K\|v;{}$\6
${}\|t\MG\\{rlink}\K\|v;{}$\6
\4${}\}{}$\2\par
\fi

\M{19}\B\X16:Priority queue procedures\X${}\mathrel+\E{}$\6
\&{Vertex} ${}{*}\\{del\_first}(\,){}$\1\1\2\2\6
${}\{{}$\5
\1\&{Vertex} ${}{*}\|t;{}$\7
${}\|t\K\\{head}\MG\\{rlink};{}$\6
\&{if} ${}(\|t\E\\{head}){}$\1\5
\&{return} ${}\NULL;{}$\2\6
${}(\\{head}\MG\\{rlink}\K\|t\MG\\{rlink})\MG\\{llink}\K\\{head};{}$\6
\&{return} \|t;\6
\4${}\}{}$\2\par
\fi

\N{1}{20}A special case. When the arc lengths in the graph are all fairly
small,
we can substitute another queueing discipline that does each operation
quickly. Suppose the only lengths are 0, 1, \dots,~$\|k-\T{1}$; then we can
prove easily that the priority queue will never contain more than \|k
different values at once. Moreover, we can implement it by maintaining
\|k doubly linked lists, one for each key value mod~\|k.

For example, let $\|k\K\T{128}$.  Here is an alternate set of queue commands,
to be used when the arc lengths are known to be less than~128.

\fi

\M{21}\B\X16:Priority queue procedures\X${}\mathrel+\E{}$\6
\&{long} \\{master\_key};\C{ smallest key that may be present in the priority
queue }\7
\&{void} \\{init\_128}(\|d)\1\1\6
\&{long} \|d;\2\2\6
${}\{{}$\5
\1\&{register} \&{Vertex} ${}{*}\|u;{}$\7
${}\\{master\_key}\K\|d;{}$\6
\&{for} ${}(\|u\K\\{head};{}$ ${}\|u<\\{head}+\T{128};{}$ ${}\|u\PP){}$\1\5
${}\|u\MG\\{llink}\K\|u\MG\\{rlink}\K\|u;{}$\2\6
\4${}\}{}$\2\par
\fi

\M{22}If the number of lists were not a power of 2, we would calculate a
remainder
by division instead of by logical-anding.

\Y\B\4\X16:Priority queue procedures\X${}\mathrel+\E{}$\6
\&{Vertex} ${}{*}\\{del\_128}(\,){}$\1\1\2\2\6
${}\{{}$\5
\1\&{long} \|d;\6
\&{register} \&{Vertex} ${}{*}\|u,{}$ ${}{*}\|t;{}$\7
\&{for} ${}(\|d\K\\{master\_key};{}$ ${}\|d<\\{master\_key}+\T{128};{}$ ${}\|d%
\PP){}$\5
${}\{{}$\1\6
${}\|u\K\\{head}+(\|d\AND\T{\^7f}){}$;\C{ that's $\|d\MOD\T{128}$ }\6
${}\|t\K\|u\MG\\{rlink};{}$\6
\&{if} ${}(\|t\I\|u){}$\5
${}\{{}$\C{ we found a nonempty list with minimum key }\1\6
${}\\{master\_key}\K\|d;{}$\6
${}(\|u\MG\\{rlink}\K\|t\MG\\{rlink})\MG\\{llink}\K\|u;{}$\6
\&{return} \|t;\C{ incidentally, $\|t\MG\\{dist}\K\|d$ }\6
\4${}\}{}$\2\6
\4${}\}{}$\2\6
\&{return} ${}\NULL{}$;\C{ all 128 lists are empty }\6
\4${}\}{}$\2\par
\fi

\M{23}\B\X16:Priority queue procedures\X${}\mathrel+\E{}$\6
\&{void} ${}\\{enq\_128}(\|v,\39\|d){}$\1\1\6
\&{Vertex} ${}{*}\|v{}$;\C{ new vertex for the queue }\6
\&{long} \|d;\C{ its \\{dist} }\2\2\6
${}\{{}$\5
\1\&{register} \&{Vertex} ${}{*}\|u\K\\{head}+(\|d\AND\T{\^7f});{}$\7
${}\|v\MG\\{dist}\K\|d;{}$\6
${}(\|v\MG\\{llink}\K\|u\MG\\{llink})\MG\\{rlink}\K\|v;{}$\6
${}\|v\MG\\{rlink}\K\|u;{}$\6
${}\|u\MG\\{llink}\K\|v;{}$\6
\4${}\}{}$\2\par
\fi

\M{24}All of these operations have been so simple, one wonders why the lists
should be doubly linked. Single linking would indeed be plenty---if we
didn't have to support the \\{requeue} operation.

But requeueing involves deleting an arbitrary element from the middle of
its list. And we do seem to need two links for that.

In the application to Dijkstra's algorithm, the new \|d will always
be \\{master\_key} or more. But we want to implement requeueing in general,
so that this procedure can be used also for other algorithms
such as the calculation of minimum spanning trees (see {\sc MILES\_\,SPAN}).

\Y\B\4\X16:Priority queue procedures\X${}\mathrel+\E{}$\6
\&{void} ${}\\{req\_128}(\|v,\39\|d){}$\1\1\6
\&{Vertex} ${}{*}\|v{}$;\C{ vertex to be moved to another list }\6
\&{long} \|d;\C{ its new \\{dist} }\2\2\6
${}\{{}$\5
\1\&{register} \&{Vertex} ${}{*}\|u\K\\{head}+(\|d\AND\T{\^7f});{}$\7
${}(\|v\MG\\{llink}\MG\\{rlink}\K\|v\MG\\{rlink})\MG\\{llink}\K\|v\MG%
\\{llink}{}$;\C{ remove \|v }\6
${}\|v\MG\\{dist}\K\|d{}$;\C{ the new \\{dist} is smaller than it was before }\6
${}(\|v\MG\\{llink}\K\|u\MG\\{llink})\MG\\{rlink}\K\|v;{}$\6
${}\|v\MG\\{rlink}\K\|u;{}$\6
${}\|u\MG\\{llink}\K\|v;{}$\6
\&{if} ${}(\|d<\\{master\_key}){}$\1\5
${}\\{master\_key}\K\|d{}$;\C{ not needed for Dijkstra's algorithm }\2\6
\4${}\}{}$\2\par
\fi

\M{25}The user of {\sc GB\_\,DIJK} needs to know the names of these
queueing procedures if changes to the defaults are made, so we'd
better put the necessary info into the header file.

\Y\B\4\X3:\.{gb\_dijk.h }\X${}\mathrel+\E{}$\6
\&{extern} \&{void} \\{init\_dlist}(\,);\6
\&{extern} \&{void} \\{enlist}(\,);\6
\&{extern} \&{void} \\{reenlist}(\,);\6
\&{extern} \&{Vertex} ${}{*}\\{del\_first}(\,);{}$\6
\&{extern} \&{void} \\{init\_128}(\,);\6
\&{extern} \&{Vertex} ${}{*}\\{del\_128}(\,);{}$\6
\&{extern} \&{void} \\{enq\_128}(\,);\6
\&{extern} \&{void} \\{req\_128}(\,);\par
\fi

\N{1}{26}Index. Here is a list that shows where the identifiers of this program
are
defined and used.

\fi


\inx
\fin
\con
