Некоторые методы расчёта диаметра графа:

• Алгоритм кратчайшего пути. 1 Позволяет найти кратчайшие пути между всеми парами вершин, а затем использовать максимальное из вычисляемых расстояний. 1 Например, в графе с положительными весами рёбер для этого можно многократно использовать алгоритм Дейкстры, по одному разу для каждой возможной начальной вершины. 1
• Алгоритм, основанный на быстром умножении матриц. 1 Время вычисления пропорционально времени умножения матриц n×n, приблизительно O (n 2.37) с использованием известных алгоритмов умножения матриц. 1
• Алгоритм Флойда-Уоршелла. 2 Позволяет найти все кратчайшие пути между каждой парой вершин, считается, что веса рёбер единичные. 2 Работает и для ориентированного графа. 2
• Алгоритм приближённой функции окрестности. 3 Позволяет приближённо вычислить радиус и диаметр графа, при этом поиск расстояний между вершинами графа производится с некоторой погрешностью. 3
• Методы для специальных классов графов. 1 Например, диаметр можно вычислить за линейное время для интервальных графиков и за почти линейное время для графиков ограниченной древовидной ширины. 1