### Minimum-cost flow – Successive shortest path algorithm

Given a network $G$ consisting of $n$ vertices and $m$ edges. For each edge (generally speaking, oriented edges, but see below), the capacity (a non-negative […]

Given a network $G$ consisting of $n$ vertices and $m$ edges. For each edge (generally speaking, oriented edges, but see below), the capacity (a non-negative […]

1. Overview In a normal flow network the flow of an edge is only limited by the capacity $c(e)$ from above and by 0 from […]

MPM (Malhotra, Pramodh-Kumar and Maheshwari) algorithm solves the maximum flow problem in $O(V^3)$. This algorithm is similar to Dinic’s algorithm. 1. Algorithm Like Dinic’s algorithm, MPM […]

Dinic’s algorithm solves the maximum flow problem in $O(V^2E)$. The maximum flow problem is defined in this article Maximum flow – Ford-Fulkerson and Edmonds-Karp. This algorithm […]

We will modify the push-relabel method to achieve a better runtime. 1. Description The modification is extremely simple: In the previous article we chosen a vertex with […]

The push-relabel algorithm (or also known as preflow-push algorithm) is an algorithm for computing the maximum flow of a flow network. The exact definition of […]

The Edmonds-Karp algorithm is an implementation of the Ford-Fulkerson method for computing a maximal flow in a flow network. 1. Flow network First let’s define […]

We have a tree $G$ with $n$ nodes and we have $m$ queries of the form $(u, v)$. For each query $(u, v)$ we want […]

Given an array A[0..N-1]. For each query of the form [L, R] we want to find the minimum in the array A starting from position L and ending with position R. We will […]

Let $G$ be a tree. For every query of the form $(u, v)$ we want to find the lowest common ancestor of the nodes $u$ […]

Let $G$ be a tree. For every query of the form (u, v) we want to find the lowest common ancestor of the nodes u and v, i.e. we want […]

1. Lowest Common Ancestor – $O(\sqrt{N})$ and $O(\log N)$ with $O(N)$ preprocessing Given a tree $G$. Given queries of the form $(v_1, v_2)$, for each […]

A Eulerian path is a path in a graph that passes through all of its edges exactly once. A Eulerian cycle is a Eulerian path […]

You are given a directed weighted graph $G$ with $N$ vertices and $M$ edges. Find any cycle of negative weight in it, if such a […]

Consider a directed or undirected graph without loops and multiple edges. We have to check whether it is acyclic, and if it is not, then […]

In this article we will look at the so-called Prüfer code (or Prüfer sequence), which is a way of encoding a labeled tree into a sequence of […]

Problem: You are given a connected undirected graph (with possible multiple edges) represented using an adjacency matrix. Find the number of different spanning trees of […]

A Minimum Spanning Tree $T$ is a tree for the given graph $G$ which spans over all vertices of the given graph and has the […]

For an explanation of the MST problem and the Kruskal algorithm, first see the main article on Kruskal’s algorithm. In this article we will consider the […]

Given a weighted undirected graph. We want to find a subtree of this graph which connects all vertices (i.e. it is a spanning tree) and […]