Dijkstra Algorithm

2021 VietMX 3

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

2021 VietMX 0

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 Bridges Online

2021 VietMX 0

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 […]

Depth First Search

2021 VietMX 11

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

2021 VietMX 4

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 […]

Vertical decomposition

2021 VietMX 0

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 […]