# Dijkstra's algorithm (Inform 7)

Dijkstra's algorithm is a graph algorithm that simultaneously finds the **shortest path** from a single vertex in a weighted graph to all other vertices in the graph, called the single-source shortest path problem. It works for directed and undirected graphs, but unlike the Bellman-Ford algorithm, requires nonnegative edge weights.

## Contents |

## [edit] theory

We use the relation support in Inform 7 to code a well-known graph algorithm. Inform 7 is somewhat reminiscent of a cross between Prolog, COBOL, and DDL — with the interesting property that phrases such as *the nearest examined node contacting the current node* may serve both as specification and as executable code.

## [edit] practice

### [edit] Dijkstra's algorithm

Dijkstra's algorithm is a greedy algorithm that divides nodes up into three types:

- nodes for which we have definitely
**found**the shortest path - nodes which we have
**examined**, which have a shortest path thus far seen - and, nodes which are yet
**unreached**

We start by examining the source node, by definition at distance 0, with all the rest as yet *unreached*. Then we repeatedly run examination steps until converging by running out of *examined* nodes to consider. On each iteration, we greedily convert the **nearest examined** node to a **found** node, and then examine all of its neighbors — **the nodes contacting n**.

<<dijkstra's algorithm>>=Every turn: run Dijkstra's algorithm. To run Dijkstra's algorithm: initialize Dijkstra's algorithm from the current node; while some of the nodes are examined begin; continue Dijkstra's algorithm; end while. To initialize Dijkstra's algorithm from (n - a node): clear the state; now n is examined; change the total distance of n to 0. To continue Dijkstra's algorithm: let n be the nearest examined node; now n is found; repeat with m running through the nodes contacting n begin; examine m from n; end repeat.

when we **examine** a path to a node, it may

- already have a confirmed shortest path
- be the first time we have encountered the node
- or, already have a provisional shortest path

in which case, we

- ignore it (perform a NOP to keep Inform happy)
- set its
**total distance**and add it to the**examined**set along with a back-pointer - or, do the above only if the new
**total distance**would be shorter than the old.

<<dijkstra's algorithm>>=To examine (m - a found node) from (n - a node): now m is found. To examine (m - an unreached node) from (n - a node): now m is examined; change the total distance of m to the extension of n to m; now m follows n. To examine (m - an examined node) from (n - a node): let d be the extension of n to m; if the total distance of m > d begin; change the total distance of m to d; now m follows n; end if.

some ancillary details:

<<dijkstra's algorithm>>=To clear the state: repeat with m running through nodes begin; now m is unreached; now m does not follow anything; end repeat; To decide what number is the extension of (n - a node) to (m - a node): decide on the total distance of n + the distance between m and n.

### [edit] definitions

There are a number of definitions we need to make for the code above to run — both static properties, which are a function of the given graph:

- defining
**contact**allows us to repeat over**nodes contacting n**. - as it is constant, we will initialize the contact relation once,
**when play begins**.

<<node properties>>=A node is a kind of thing. Contact relates nodes to each other. The verb to contact (he contacts, they contact, he contacted, it is contacted, he is contacting) implies the contact relation.

and dynamic properties, which will change when we change the source node.

- the
**total distance**holds the the length of the (currently estimated) shortest path from the source node. - the
**10**in the definition of**near**is arbitrary — we provide this definition only so that we may use the superlative, and ask for the**nearest examined node**when we**continue Dijkstra's algorithm**. - defining the
**precedent**allows us to extract the full path (in reverse order) to any given node from the source node.

<<node properties>>=The current node is a node that varies. A node can be found, examined, or unreached. A node has a number called the total distance. Definition: a node is near if its total distance is 10 or less. Following relates various nodes to one node (called the precedent). The verb to follow (he follows, they follow, he followed, it is followed, he is following) implies the following relation.

### [edit] test data

We use the test data from Dijkstra's algorithm (Scala), and add Oxford, the home of Inform 7. It may be possible to key on multiple fields, but as the table is small, here we take the brute-force approach of performing a symmetric scan.

<<test data>>=Barcelona, Geneve, Lausanne, London, Marseille, Narbonne, Oxford, Paris, and Toulouse are nodes. Table of Intercity Distances src dst distance Barcelona Narbonne 250 Geneve Lausanne 64 Geneve Marseille 260 Geneve Narbonne 550 Geneve Paris 540 Geneve Toulouse 700 Lausanne Paris 536 London Oxford 95 London Paris 440 Marseille Narbonne 260 Narbonne Toulouse 150 Paris Toulouse 680 To decide what number is the distance between (n - a node) and (m - a node): repeat through the Table of Intercity Distances begin; if the src entry is n and the dst entry is m, decide on the distance entry; if the src entry is m and the dst entry is n, decide on the distance entry; end repeat.

### [edit] interaction

In order to provide output and accept user input, we must make a few more definitions. The recursion runs from the desired node back to the current node, but the output is generated upon return, yielding the path in-order from current to desired.

<<user interaction>>=Definition: a node is initial if it is the current node. To slide the marker from (n - an initial node): say "You take the marker from [n] and slide it". To slide the marker from (n - a node): slide the marker from the precedent of n; say " to [n]". To slide the marker to (n - a node): slide the marker from the precedent of n; say ", winding up at [n].". planning is an action applying to one visible thing. understand "[a node]" as planning. check planning: if the current node is the noun, say "The marker is already at [the current node]." instead. carry out planning: slide the marker to the noun; change the current node to the noun.

## [edit] wrapping up

Finally we complete the game with the authoring boilerplate, an initial room for the player, some initialization code, and a small test-suite.

<<dijkstra.inform7>>="Dijkstra's Algorithm" by Dave node properties dijkstra's algorithm test data user interaction The Map Room is a room. "You are looking at a roadmap centered on the south of France[line break]Say 'relations' to examine the current graph state[line break]Say 'city name' to plan a trip from [the current node].". The marker and the roadmap are scenery in the Map Room. When play begins: repeat through the Table of Intercity Distances begin; now the src entry contacts the dst entry; now the dst entry contacts the src entry; end repeat; repeat with n running through the nodes begin; move n to the Map Room; end repeat; change the current node to Barcelona; run Dijkstra's algorithm. Test me with "barcelona/lausanne/barcelona/paris/marseille"

A sample run is as follows:

Map Room You are looking at a roadmap centered on the south of France Say "city name" to plan a trip from Barcelona. You can see Toulouse, Paris, Narbonne, Marseille, Lausanne, Geneve and Barcelona here. > barcelona The marker is already at Barcelona. > lausanne You take the marker from Barcelona and slide it to Narbonne to Marseille to Geneve, winding up at Lausanne. > barcelona You take the marker from Lausanne and slide it to Geneve to Marseille to Narbonne, winding up at Barcelona. > paris You take the marker from Barcelona and slide it to Narbonne to Toulouse, winding up at Paris. > marseille You take the marker from Paris and slide it to Geneve, winding up at Marseille. >

Download code |