Algorithms Catalogue

Algorithms Catalogue

1 Wayfinding

1.1 A*

Algorithm	A*
Description	The most common algorithm for quickly finding one of the best routes from a source to a destination
Measures	Given a current location and a target location, A* can deliver a path as a series of target nodes. A modified A* algorithm can add additional journey requirements if these are incorporated into the model, e.g. traffic/occupancy, accessibility etc.
Models	A* requires that the space to be traversed is represented as an array of linked lists, so that each node (location) has a list of reachable nodes, with each vertex containing information such as travel time accessibility, congestion etc. A* can also use a square grid system, where each node is a square taken from a map and marked as passable/impassable, for example from scanning a real-world map.
Examples

1.2 BFS

Algorithm	BFS - Breadth First Search
Description	A common algorithm for quickly finding a route from a source to a destination. BFS is fast and always returns the path with the smallest number of steps, but is primarily useful for unweighted graphs.
Measures	Given a current location and a target location, BFS can deliver a path as a series of target nodes.
Models	BFS requires that the space to be traversed is represented as an array of arrays, so that each node (location) has a list of reachable nodes. This means it can be used with very simple data models consisting of locations with a list of adjacent locations.
Examples

1.3 Dijkstra's algorithm

Algorithm	Dijkstra's algorithm
Description	One of the first wayfinding algorithms. For a given source node in the graph, the algorithm finds the shortest path between that node and every other. It can also be used for finding the shortest paths from a single node to a single destination node by stopping the algorithm once the shortest path to the destination node has been determined.
Measures
Models	The algorithm requires that the space is represented as a set of nodes and vertices with travel time (or some other factor) on each vertex.
Examples

1.4 ACO

Algorithm
Description
Measures
Examples

1.5 A* with Knowledge Levels

Combines a heuristic pathfinding algorithm such as A* with multiple levels of knowledge within the representation. For example, first running A* to find the shortest route between buildings, then again to find the shortest route within the target building.