Djikstra's algorithm (named
after its discover, E.W. Dijkstra) solves the problem of finding the shortest
path from a point in a graph (the source) to a destination. It turns out that one
can find the shortest paths from a given source to all points in a graph in the
same time, hence this problem is sometimes called the single-source shortest
paths problem.
This problem is related to
the spanning tree one. The graph representing all the paths from one vertex to
all the others must be a spanning tree - it must include all vertices. There
will also be no cycles as a cycle would define more than one path from the
selected vertex to at least one other vertex.
Path information can be
obtained simply by creating an instance of DijkstraPath:
local path = new DijkstraPath(actor, source, destination);
This returns a DijkstraPath
object that encapsulates the following data:
Much of this information is
redundant, providing a slightly different perspective of the information
provided by dijkstra’s algorithm. For instance, an author defining an automated
actor that moves from room to room may decide that the shortestPathVertexList
is sufficient for his needs; another author may feel that the
shortestPathEntryList is preferable as it contains further information
regarding known edges; and yet another author may wish to adopt the TravelLink
viewpoint.
The Entry class is the basic
unit used in the dijkstra computation. Beside this basic information, the class
encapsulates:
§
a list of DestInfo class objects for the given vertex
§
a list of DestInfo class objects that are known to this actor
§
a list of entries adjacent to this one
§
a list of all the
travelEdges that would lead from this vertex to the next one in
the shortest path.
The TravelLink class provides a useful alternative viewpoint of the
data, and encapsulates the following information:
§
currTravelNode – the vertex that is the predecessor to another vertex in the shortestPathEntryList
§
nextTravelNode – the vertex that currTravelNode
is the predecessor of in the shortestPathEntryList
§
travelEdgeList – a list of all the edges logically connecting the currTravelNode to the nextTravelNode
The DijkstraPath computation formulates a logical path that relies on actor knowledge about the travel graph.
To do so the actor must be
familiar with the locations that form the vertices used in the computation.
Each actor possesses a locationMemory LookupTable to facilitate
storage and retrieval of the actor’s knowledge of a given vertex. By default an
actor has no knowledge of the vertices of the travel graph, which means that no
dijkstra path can be calculated to any destination. Authors should load the locationMemory LookupTable with the
locations for which the actor should have an initial knowledge.
The final bit of actor
knowledge that DijkstraPath makes use of is the actor’s previous knowledge of the success or failure of a
given edge from a given vertex. By default the travelBlocked(loc, dir) method returns
nil. Some authors may wish to implement a travelEdgeMemory
system that keeps track of the results of the physical traversal of the Connector, to
compare it with the logical
(apparent) connection that is based on the actor’s initial knowledge.
This file is part of the TADS 3
Proteus Library Extension
Copyright ©
2001-2004 Kevin Forchione.