List of Algorithms

This is a list of well-known or widely applicable algorithms.

Note: Variants should be linked to from their related pages, and less well-known and/or applicable algorithms should find another home.

Graph algorithms

• AStarAlgorithm - Finds the shortest path between a starting node and a destination node, using a heuristic to search the best candidate paths first.
• ArticulationPoints
• BellmanFordAlgorithm - Finds the shortest path between a starting node and all other nodes in a graph.
• BipartiteMatching - Finds the maximal pairing of a bipartite graph.
• BreadthFirstSearch - Visits every node in a graph in the order that the nodes are discovered.
• BrigdesAndBiconnectedComponents
• CountingSpanningTrees - Counts the number of distinct spanning trees possible for a graph.
• DepthFirstSearch - Visits every node in a graph, following a path for as long as possible before backtracking.
• DijkstrasAlgorithm - Finds the shortest path between a starting node and all other nodes in a graph.
• EdmondsAlgorithm - Finds a minimum/maximum spanning tree on a directed graph.
• EulerianCircuit - Finds a circuit of a graph that visits every edge exactly once.
• FloydWarshallAlgorithm - Finds the shortest path between every pair of nodes in a graph.
• FloydsCycleFindingAlgorithm - Finds cycles in a sequence of values.
• FordFulkersonAlgorithm - Finds the maximum flow through a network.
• GraphColouringAlgorithm - Partitions the vertices of a graph so that adjacent vertices are not in the same partition.
• MaximalCliques - Finds all maximal cliques in a graph.
• MinimumRadiusSpanningTree - Finds the spanning tree of a graph that minimises the maximum path length from the root to each leaf node.
• PrimsAlgorithm - Finds the minimal spanning tree of a weighted graph.
• StoerWagnerMinCut
• StronglyConnectedComponents - Finds sets of vertices in a directed graph such that each vertex in the set has a path to each other vertex.
• TarjansOfflineLeastCommonAncestor
• TopologicalSort - Finds a linear ordering of items which have a partial ordering defined over them.
• WelshPowellAlgorithm - Colours a graph with at most one colour more than the maximum degree of a graph.

Geometric algorithms

• AngleBetweenTwoVectors - Finds the angle between two vectors.
• CircumcircleOfTriangle - Finds the circle that intersects all points of a triangle.
• ClosestApproachLineSegmentToPoint - Finds the point on a line segment closest to a given point.
• ClosestApproachLineToPoint - Finds the point on a line closest to a given point.
• ClosestApproachPlaneToPoint - Finds the point on a plane closest to a given point.
• ColinearPointBetweenTwoOthers - Determines whether a point that is known to be colinear to two other points is between those two points.
• ConvexPolygonIntersection
• CrossingNumber
• GrahamsScan - Finds the convex hull of a set of points.
• LineIntersection - Finds the point where two lines intersect.
• LineIntersectsPlane - Finds the point where a line intersects a plane.
• LineRepresentations - Convert between representations of a line.
• LineSegmentIntersection - Finds the point where two line segments intersect.
• MinimumEnclosingCircleOfPoints - Finds the smallest circle that contains a set of points.
• PicksTheorem - Finds the area of a simple polygon with integer boundary points.
• PointInPolygon - Determines whether a point is inside a polygon.
• RegionTree
• RotatingCallipers - Finds the antipodal pairs of points and vertices on a convex polygon.
• SimplePolygonArea - Finds the area of a simple polygon.
• SimplePolygonCentreOfMass - Finds the centre of mass of a simple polygon.
• TriangulateSimplePolygon - Decomposes a simple polygon into disjoint triangles.
• WindingNumber

String algorithms

• BoyerMoore - Locates occurrences of a pattern within a string.
• BurrowsWheelerTransform - Permutes a string to increase repeated characters and improve data compression rates.
• DeBruijnSequence - Gives a sequence of characters from an alphabet in which each subsequence of n characters appears exactly once.
• KnuthMorrisPratt - Locates occurrences of a pattern within a string.
• RabinKarp - Locates occurrences of a set of patterns within a string.
• SuffixArray - Gives an array containing the starting index of each possible suffix of a string, sorted by lexicographical order.

Numerical / combinatorial algorithms

• CatalanNumbers
• ChangsQuotientAlgorithm
• ChineseRemainderTheorem - Solves for a number given its remainder modulo a list of coprime numbers.
• DurandKernerAlgorithm - Finds the roots of a polynomial.
• EulersTotientFunction
• ExtendedEuclidsAlgorithm - Finds the minimal solution to sa + tb = gcd(a, b).
• GaussianElimination - Reduces a matrix to row echelon form, used to solve systems of linear equations and find matrix inverses.
• HornersRule - Fast method to evaluate polynomials.
• LexicographicalRankOfPermutations - Finds the index of a permutation in the lexicographically sorted sequence of all possible permutations.
• LinearProgramming - Optimises a linear function in many variables given a set of linear constraints.
• LUDecomposition - Decomposes a matrix into a product of upper- and lower-triangular matrices, used to efficiently calculate the determinant.
• MatrixDeterminant - Finds the matrix determinant.
• ModularInverse - Finds x in ax - 1 (mod n)
• NextCombinationColexicographicalOrder
• NextIntegerKPartitionInLexicographicalOrder
• NextIntegerPartitionInReverseOrder
• PartialFractions
• PascalsTriangle - Combinations of n take r.
• PolynomialOperations - Polynomial division, multiplication and GCD.
• PrimeFactorisation
• RCombinationsInLexicographicalOrder
• SystemOfModularEquations - Solves equations of the form ax - b (mod n)

Dynamic programming

• CoinChangeMinimumNumberOfCoins - Finds the minimum number of coins that make up an amount of money from a number of coins.
• CoinChangeWaysToMakeSum - Finds the number of ways to make up an amount of money from a number of coins.
• EditDistance - Finds the least number of insertions, deletions and substitutions required to change one string to another.
• FloydWarshallAlgorithm - Finds the shortest path between every pair of nodes in a graph.
• KnapsackProblem - Finds a combination of a finite number of items, which have the greatest total value given a constraint on the total size of the items.
• LongestCommonSubsequence - Finds the longest subsequence that appears in the same order in two supersequences.
• LongestIncreasingSequence - Finds the longest subsequence of a sequence, whose elements appear in an increasing order.
• MatrixMultiplicationOrder - Finds a bracketing for a series of matrix multiplications that minimises the work done.
• MaximumIntervalSum - Finds an interval in a sequence of numbers that has the maximum sum.
• ShortestCommonSupersequence

Other

• StableMarriageProblem