Minimum spanning tree – Prim’s algorithm
Given a weighted, undirected graph $G$ with $n$ vertices and $m$ edges. You want to find a spanning tree of this graph which connects all […]
ACM
Number of paths of fixed length / Shortest paths of fixed length
The following article describes solutions to these two problems built on the same idea: reduce the problem to the construction of matrix and compute the […]
Floyd-Warshall – finding all shortest paths
Given a directed or an undirected weighted graph $G$ with $n$ vertices. The task is to find the length of the shortest path $d_{ij}$ between […]
D´Esopo-Pape algorithm
Given a graph with $n$ vertices and $m$ edges with weights $w_i$ and a starting vertex $v_0$. The task is to find the shortest path […]
Bellman-Ford Algorithm
Single source shortest path with negative weight edges Suppose that we are given a weighted directed graph $G$ with $n$ vertices and $m$ edges, and […]
Dijkstra on sparse graphs
For the statement of the problem, the algorithm with implementation and proof can be found on the article Dijkstra’s algorithm. 1. Algorithm We recall in the […]
Dijkstra Algorithm
You are given a directed or undirected weighted graph with $n$ vertices and $m$ edges. The weights of all edges are non-negative. You are also […]
Strong Orientation
A strong orientation of an undirected graph is an assignment of a direction to each edge that makes it a strongly connected graph. That is, after the orientation we should […]
Finding strongly connected components – Building condensation graph
1. Definitions You are given a directed graph $G$ with vertices $V$ and edges $E$. It is possible that there are loops and multiple edges. […]
Finding articulation points in a graph in $O(N+M)$
We are given an undirected graph. An articulation point (or cut vertex) is defined as a vertex which, when removed along with associated edges, makes […]
Finding Bridges Online
1. Overview We are given an undirected graph. A bridge is an edge whose removal makes the graph disconnected (or, more precisely, increases the number […]
Finding bridges in a graph in $O(N+M)$
We are given an undirected graph. A bridge is defined as an edge which, when removed, makes the graph disconnected (or more precisely, increases the […]
Search for connected components in a graph
Given an undirected graph $G$ with $n$ nodes and $m$ edges. We are required to find in it all the connected components, i.e, several groups […]
Depth First Search
Depth First Search is one of the main graph algorithms. Depth First Search finds the lexicographical first path in the graph from a source vertex […]
Breadth-first search
Breadth first search is one of the basic and essential searching algorithms on graphs. As a result of how the algorithm works, the path found […]
Half-plane intersection – S&I Algorithm in O(Nlog N)
In this article we will discuss the problem of computing the intersection of a set of half-planes. Such an intersection can be conveniently represented as […]
Vertical decomposition
1. Overview Vertical decomposition is a powerful technique used in various geometry problems. The general idea is to cut the plane into several vertical stripes […]
Delaunay triangulation and Voronoi diagram
1. Overview Consider a set $\{p_i\}$ of points on the plane. A Voronoi diagram $V(\{p_i\})$ of $\{p_i\}$ is a partition of the plane into $n$ regions $V_i$, […]
Finding the nearest pair of points
1. Problem statement Given $n$ points on the plane. Each point $p_i$ is defined by its coordinates $(x_i,y_i)$. It is required to find among them […]
