Path search

IMP.bff implements a set of graph traversal algorithms to find optimal paths from a starting node to end nodes in the presence of obstacles. Here, nodes are points on a grid around a starting node. Obstacles are usually atoms, residues, or proteins (e.g., represented as rigid bodies). If path map used in label-based distance experiment, the starting node is (usually) a attachment site of a label. IMP.bff implements the Dijkstra’s and the A* algorithm for finding the shortest paths between nodes in a graph.

Dijkstra’s algorithm

The Dijkstra’s algorithm finds for a given source (start) node in the graph the shortest path between that node and every other node. 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.

A star

The A* (pronounced “A-star”) algorithm is a graph traversal and path search algorithm that finds an optimal path between a source (start) node and a target node. A* can be seen as an extension of Dijkstra’s algorithm that achieves better performance by using heuristics to guide its search.

Applications

The path algorithms are used to compute

• Accessible volumes

• Surface distances

• Inter-label distance restraints

Programming examples are

• Path search

• Distance maps

• Distance maps

• AV restraint

• Scoring with AV restraints

• IMP AV decorator