Dijkstra

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.

Computing the DijkstraPath

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:

startingVertex – the source required by the new statement
targetVertex – the destination required by the new statement
entryList – a list of all entries computed by the algorithm
reachableEntryList – a list of all entries logically reachable by travel for the actor
shortestPathEntryList – a list of all entries that constitute the shortest path from source to destination for this actor
shortestPathVertexList – a list of all vertices that constitute the shortest path from source to destination for this actor
travelLinkList – a list of all travelLinks that constitute the shortest path from source to destination for this actor

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.

Entry

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.

TravelLink

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

Actor Knowledge

The DijkstraPath computation formulates a logical path that relies on actor knowledge about the travel graph.

Location Memory

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.

Logical Destination Information

Additionally, DijkstraPath makes use of the actor’s getExitsList() method to build a list of DestInfo class objects that reflect the logical (apparent) destinations for each Direction defined on the vertex under inspection. The method is similar to that used by the exitLister for displaying the exits from a BasicLocation, but takes only a location and a variable argument list (computingPath) as parameters. If true is passed in the variable arguments list then the apparent nature of Connectors as well as lighting considerations are bypassed in the determination; otherwise nil indicates that these elements should be taken into consideration. It is recommended that when calculating a logical path computingPath should be true.

Blocked Travel

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