В качестве входа служит ориентированный граф, т.е. множество вершин V и множество рёбер (т.е. пар вершин) E.

Вершина w достижима из вершины v, если существует последовательность вершин x₁, ..., x_n такая, что рёбра (v, x₁), (x₁, x₂), ..., (x_n, w) принадлежат E. Если это кратчайшая возможная последовательность, то n+1 называется расстоянием от v до w.

Под компонентой сильной связности (далее: компонентой) вершины понимается максимальное подмножество вершин, любая из вершин которого достижима из всех остальных. Очевидно, каждая вершина принадлежит ровно одной компоненте. Будем предполагать, что для каждой вершины исходного графа дана компонента, которой она принадлежит.

Требуется для каждой вершины графа v найти:

• Любую наиболее удалённую от v вершину (т.е. расстояние до которой от v максимально);
• Эксцентриситет v (расстояние от v до наиболее удалённой вершины);
• Среднее расстояние от v до всех вершин;

ограничиваясь при выборе вершин и рёбер компонентой, которой принадлежит v.