- Shortest Path - Finds the shortest/cheapest path between two vertices.
Finding shortest paths between every pair of vertices
- Minimal Spanning Tree - Finds a connected ayclic subgraph that contains all vertices of the graph and has the smallest sum of
costs of its edges.
- Eulerian Path/Circuit - Finds a path/circuit that visits every edge exactly once.
- Chinese Postman Problem - Finds a circuit of minimum cost that starts and ends at selected vertex, passing through each edge
at least once.
- Hamiltonian Path/Circuit - Finds a path/circuit that passes through each vertex exactly once.
- Maximum Flow - Finds the maximum amount of flow (e.g. water) that can flow from start vertex (source) to destination vertex (sink).
- Maximum Flow of Minimum Cost - Finds the maximum amount of flow (e.g. water) that can flow from start vertex (source) to destination
vertex (sink) with minimum cost.
- Minimum Cut - Finds the minimum number of edges that must be cut (deleted) so that start vertex is isolated from destination
vertex (i.e. they are not connected directly or indirectly).
- Maximal Subset of Independent Vertices - Finds the largest subset of vertices that don't have any edge between them.
- Maximum Clique (complete subgraph) - Finds the largest subset of vertices that are connected all to each other.
- Optimal Graph Coloring - Colors the graph with a minimum number of colors, so that no two neighbour vertices have the same color.
- Graph Median - Finds the vertex for which the sum of lengths of shortest paths to all other vertices is the smallest.
- Graph Center - Finds the vertex for which the length of shortest path to the farthest vertex is the smallest.