Finds connected components in a graph using iterated Breadth-First-Search (BFS).

A recursive implementation of Depth-First-Search (DFS), which computes a DFS labeling.

An iterative implementation of Breadth-First-Search (BFS), which computes a BFS labeling.

Converting the iterative BFS implementation to an iterative DFS implementation by exchanging the Queue for a Stack.

An iterative implementation of Depth-First-Search (DFS), which computes a DFS labeling.

A primal dual version of Kruskal's Algorithm.

Dijkstra's algorithm for finding a shortest path tree in a graph. This is an example of a label setting algorithm.

Dijkstra's algorithm for finding a shortest path tree in a graph implemented using a Priority Queue.

A variant of Dijkstra's algorithm for finding a shortest s-t path in a graph. Terminates early, as soon as a shortest s-t path has been found.

A variant of Dijkstra's algorithm for finding a shortest s-t path in an Euclidean graph (edge weights correspond to Euclidean distance between vertices). Terminates early, as soon as a shortest s-t path has been found and only visits a small part of the graph. Similar ideas are used in A*-type algorithms.

Bellman and Ford's algorithm for finding a shortest path tree in a graph with a label correcting approach.

Most shortest path algorithms require that graphs do not have negative circuits. This algorithms detects negative circuits in a graph.

Finding a path can be accelerated by searching from start and destination simultaneously.

The Ford-Fulkerson algorithm finds a maximal flow in a capacitated network by successive shortest path applications.

The Preflow Push algorithm due to Goldberg and Tarjan computes a maximal flow by saturating a network and correcting possible excesses later.

This algorithm considers vertices as points in 2-dimensional space and implicitly assumes the existence of all edges in the complete graph. Furthermore, edge weights are Euclidean. It finds a matching of minimal weight. The matching is perfect if the number of vertices is even