| author(s) | date | JDSL version |
|---|---|---|
| Ulrik Brandes | 07/99 | 2.0 |
Summary: The implementation of Dijkstra's algorithm for the
single source shortest paths problem provided in JDSL 2.0 is based
completely on the template method pattern.
Even edge weights have to be specified by overriding a
designated method in
IntegerDijkstraTemplate.
We here outline an alternative approach using
data accessors
and allowing to control the execution from outside of the class.
This alternative implementation (source) of Dijkstra's algorithm for the single source shortest paths problem differs from the release version in mainly two ways:
VertexIterator interface to
give fine-level control over the execution to the outside class
invoking the algorithm.
Data access:
Edge weights are accessed via template hook weight(Edge)
in class IntegerDijkstraTemplate. This way,
the implementation does not depend on any form of organization of
edge weights, they may even be non-materialized. However, to make use
of the implementation, it must be subclassed. Things become
complicated, when different customizations, possibly written by other
authors, have to be combined.
The use of data accessors eliminates the need for subclassing,
while retaining the advantage of abstracting from the specific form of
edge weight representation. Moreover, distances are returned
through data accessors as well, resulting in a more uniform treatment
and thus easier use of output attributes as input for other algorithms.
Execution control:
Implementation of the VertexIterator interface
allows to execute one elementary step of Dijkstra's algorithm
at a time. Note that, due to the algorithm's nature, the iterator
enumerates the vertices in non-decreasing distance from the source.
What is more important is that execution can be interrupted or
terminated by the calling class after finding any vertex, again
without the subclassing that is mandatory for early termination hook
shouldContinue().
To allow even more flexibility, the algorithm can be parameterized
with a priority queue that can then be modified after any iteration.
Such customizations may be deemed dangerous, because they can screw up
badly the intended results. However, what may be called execution
safety seems to be a different case than, e.g., type safety.
Since there is no need for customization in standard usage of the
class, whoever customizes the algorithm does so knowingly and can thus
be held responsible for his/her mistakes. Or put another way,
failures here are due to a lack of understanding of the algorithm's
behavior rather than sloppy usage.