Back to Dijkstra's_algorithm_(Inform_7)
1 [ The authors of this work have released all rights to it and placed it 2 in the public domain under the Creative Commons CC0 1.0 waiver 3 (http://creativecommons.org/publicdomain/zero/1.0/). 4 5 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 6 EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 7 MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. 8 IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY 9 CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, 10 TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE 11 SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 12 13 Retrieved from: http://en.literateprograms.org/Dijkstra's_algorithm_(Inform_7)?oldid=19116 14 ] 15 16 "Dijkstra's Algorithm" by Dave 17 18 A node is a kind of thing. 19 Contact relates nodes to each other. 20 The verb to contact (he contacts, they contact, he contacted, it is contacted, he is contacting) implies the contact relation. 21 The current node is a node that varies. 22 23 A node can be found, examined, or unreached. 24 A node has a number called the total distance. 25 Definition: a node is near if its total distance is 10 or less. 26 27 Following relates various nodes to one node (called the precedent). 28 The verb to follow (he follows, they follow, he followed, it is followed, he is following) implies the following relation. 29 Every turn: run Dijkstra's algorithm. 30 31 To run Dijkstra's algorithm: 32 initialize Dijkstra's algorithm from the current node; 33 while some of the nodes are examined begin; 34 continue Dijkstra's algorithm; 35 end while. 36 37 To initialize Dijkstra's algorithm from (n - a node): 38 clear the state; 39 now n is examined; 40 change the total distance of n to 0. 41 42 To continue Dijkstra's algorithm: 43 let n be the nearest examined node; 44 now n is found; 45 repeat with m running through the nodes contacting n begin; 46 examine m from n; 47 end repeat. 48 49 To examine (m - a found node) from (n - a node): now m is found. 50 51 To examine (m - an unreached node) from (n - a node): 52 now m is examined; 53 change the total distance of m to the extension of n to m; 54 now m follows n. 55 56 To examine (m - an examined node) from (n - a node): 57 let d be the extension of n to m; 58 if the total distance of m > d begin; 59 change the total distance of m to d; 60 now m follows n; 61 end if. 62 To clear the state: 63 repeat with m running through nodes begin; 64 now m is unreached; 65 now m does not follow anything; 66 end repeat; 67 68 To decide what number is the extension of (n - a node) to (m - a node): 69 decide on the total distance of n + the distance between m and n. 70 Barcelona, Geneve, Lausanne, London, Marseille, Narbonne, Oxford, Paris, and Toulouse are nodes. 71 72 Table of Intercity Distances 73 src dst distance 74 Barcelona Narbonne 250 75 Geneve Lausanne 64 76 Geneve Marseille 260 77 Geneve Narbonne 550 78 Geneve Paris 540 79 Geneve Toulouse 700 80 Lausanne Paris 536 81 London Oxford 95 82 London Paris 440 83 Marseille Narbonne 260 84 Narbonne Toulouse 150 85 Paris Toulouse 680 86 87 To decide what number is the distance between (n - a node) and (m - a node): 88 repeat through the Table of Intercity Distances begin; 89 if the src entry is n and the dst entry is m, decide on the distance entry; 90 if the src entry is m and the dst entry is n, decide on the distance entry; 91 end repeat. 92 93 Definition: a node is initial if it is the current node. 94 To slide the marker from (n - an initial node): 95 say "You take the marker from [n] and slide it". 96 To slide the marker from (n - a node): 97 slide the marker from the precedent of n; 98 say " to [n]". 99 To slide the marker to (n - a node): 100 slide the marker from the precedent of n; 101 say ", winding up at [n].". 102 103 planning is an action applying to one visible thing. 104 understand "[a node]" as planning. 105 check planning: 106 if the current node is the noun, say "The marker is already at [the current node]." instead. 107 carry out planning: 108 slide the marker to the noun; 109 change the current node to the noun. 110 111 The Map Room is a room. 112 "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].". 113 The marker and the roadmap are scenery in the Map Room. 114 115 When play begins: 116 repeat through the Table of Intercity Distances begin; 117 now the src entry contacts the dst entry; 118 now the dst entry contacts the src entry; 119 end repeat; 120 repeat with n running through the nodes begin; 121 move n to the Map Room; 122 end repeat; 123 change the current node to Barcelona; 124 run Dijkstra's algorithm. 125 126 Test me with "barcelona/lausanne/barcelona/paris/marseille"