Method
precomputation
Articles
GRA
Algorithm
A*
Dijkstra with a hint of how far is left: the wave stretches towards the goal, and the path stays shortest.
O((V + E) log V)
2 problems
GRA
Algorithm
Contraction hierarchies
A navigator's precomputation: contract unimportant crossroads into shortcuts and find the path with two waves going up.
O((V + E′) log V)
1 problem
STR
Algorithm
Boyer–Moore
Compares from right to left and skips letters: on long patterns it reads only a small part of the text.
O(n + m)
2 problems
NUM
Algorithm
Gaussian elimination
A linear system by elimination: the pivot, LU, conditioning, sparse matrices and fill-in.
O(n³): about n³/3 multiplications for the forward pass
2 problems
Problems
Often together
graph 3 classic 3 in production 3 shortest path 2 heuristic 2 heap 2 weighted graph 2 maps and navigation 2 games 1 interviews 1 string matching 1 text editors 1