gb_dijk.w

模拟器提供了一个简单易用的平台

% This file is part of the Stanford GraphBase (c) Stanford University 1993
@i boilerplate.w %<< legal stuff: PLEASE READ IT BEFORE MAKING ANY CHANGES!
@i gb_types.w

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

\prerequisite{GB\_\,GRAPH}
@* 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].
@^Dijkstra, Edsger Wijbe@>

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 |-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.

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

@p
#include "gb_graph.h" /* define the standard GraphBase data structures */
@h@#
@<Priority queue procedures@>@;
@<Global declarations@>@;
@<The |dijkstra| procedure@>@;
@<The |print_dijkstra_result| procedure@>@;

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

@(gb_dijk.h@>=
extern long dijkstra(); /* procedure to calculate shortest paths */
#define print_dijkstra_result p_dijkstra_result /* shorthand for linker */
extern void print_dijkstra_result(); /* procedure to display the answer */

@* 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.)

@ To implement the ideas just sketched, we use several of the utility
fields in vertex records. Each vertex~|v| has a |dist| field |v->dist|,
which represents its true distance from |uu| if |v| is known; otherwise
|v->dist| represents the shortest distance from |uu| discovered so far.

Each vertex |v| also has a |backlink| field |v->backlink|, which is non-|NULL|
if and only if |v| has been seen. In that case |v->backlink| is a vertex one
step ``closer'' to |uu|, on a path from |uu| to |v| that achieves the
current distance |v->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.

@d dist z.I /* distance from |uu|, modified by |hh|,
                 appears in vertex utility field |z| */
@d backlink y.V /* pointer to previous vertex appears in utility field |y| */

@(gb_dijk.h@>=
#define dist @[z.I@]
#define backlink @[y.V@]

@ 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 |>=d|.

\]|enqueue(v,d)| puts vertex |v| in the queue and assigns it the key
value |v->dist=d|.

\]|requeue(v,d)| takes vertex |v| out of the queue and enters it again
with the smaller key value |v->dist=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.

@(gb_dijk.h@>=
extern void @[@] (*init_queue)();
 /* create an empty priority queue for |dijkstra| */
extern void @[@] (*enqueue)(); /* insert a new element in the priority queue */
extern void @[@] (*requeue)(); /* decrease the key of an element in the queue */
extern Vertex *(*del_min)(); /* remove an element with smallest key */

@ The heuristic function might take a while to compute, so we avoid
recomputation by storing |hh(v)| in another utility field |v->hh_val|
once we've evaluated it. 

@d hh_val x.I /* computed value of |hh(v)| */

@(gb_dijk.h@>=
#define hh_val @[x.I@]

@ If no heuristic function is supplied by the user, we replace it by a
dummy function that simply returns 0 in all cases.

@<Global...@>=
static long dummy(v)
  Vertex *v;
{@+return 0;@+}

@ Here now is |dijkstra|:

@<The |dijkstra| procedure@>=
long dijkstra(uu,vv,gg,hh)
  Vertex *uu; /* the starting point */
  Vertex *vv; /* the ending point */
  Graph *gg; /* the graph they belong to */
  long @[@] (*hh)(); /* heuristic function */
{@+register Vertex *t; /* current vertex of interest */
  if (!hh) hh=dummy; /* change to default heuristic */
  @<Make |uu| the only vertex seen; also make it known@>;
  t=uu;
  if (verbose) @<Print initial message@>;
  while (t!=vv) {
    @<Put all unseen vertices adjacent to |t| into the queue,
       and update the distances of other vertices adjacent to~|t|@>;
    t=(*del_min)();
    if (t==NULL)
      return -1; /* if the queue becomes empty,
                      there's no way to get to |vv| */
    if (verbose) @<Print the distance to |t|@>;
  }
  return vv->dist-vv->hh_val+uu->hh_val; /* true distance from |uu| to |vv| */
}

@ 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.

@<Make |uu| the only...@>=
for (t=gg->vertices+gg->n-1; t>=gg->vertices; t--) t->backlink=NULL;
uu->backlink=uu;
uu->dist=0;
uu->hh_val=(*hh)(uu);
(*init_queue)(0L); /* make the priority queue empty */

@ Here we help the \CEE/ compiler in case it hasn't got a great optimizer.

@<Put all unseen vertices adjacent to |t| into the queue...@>=
{@+register Arc *a; /* an arc leading from |t| */
  register long d = t->dist - t->hh_val;
  for (a=t->arcs; a; a=a->next) {
    register Vertex *v = a->tip; /* a vertex adjacent to |t| */
    if (v->backlink) { /* |v| has already been seen */
      register long dd = d + a->len + v->hh_val;
      if (dd< v->dist) {
        v->backlink = t;
        (*requeue)(v,dd); /* we found a better way to get there */
      }
    }@+else { /* |v| hasn't been seen before */
      v->hh_val = (*hh)(v);
      v->backlink = t;
      (*enqueue)(v, d + a->len + v->hh_val);
    }
  }
}

@ 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->dist - v->hh_val + uu->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