singhsumit связал соответствующий документ Хассен и Тамир , озаглавленный «О проблеме остовного дерева минимального диаметра», но его ответ в настоящее время удален. Основная идея из статьи заключается в том, что нахождение остовного дерева минимального диаметра в неориентированном графе может быть достигнуто путем нахождения «абсолютного 1-центра» графа и возврата дерева кратчайшего пути, укорененного в нем.
Абсолютный 1-центр - это точка на вершине или ребре, от которой расстояние до самой дальней вершины минимально. Это можно найти с помощью алгоритма Карива и Хакими (Алгоритмический подход к проблемам определения местоположения в сети. I: p-центры) или более раннего алгоритма Хакими, Шмейхеля и Пирса (О p-центрах в сетях), который я буду попытаться восстановить только из продолжительности и десятилетий задним числом. (Глупые стены оплаты.)
Используйте алгоритм Флойда - Варшалла или Джонсона для вычисления расстояний между парами. Для каждого ребра u - v найдите лучшего кандидата для 1-центра на этом ребре следующим образом.
Пусть точки на ребре u - v проиндексированы с помощью µ в диапазоне от 0 (сам u) до len (u - v) (сам v). Расстояние от точки с индексом µ до вершины w равно
min (µ + d (u, w), len (u - v) - µ + d (v, w)).
Как функция от µ, эта величина увеличивается, а затем уменьшается с максимумом при
µ = (len (u - v) + d (v, w) - d (u, w)) / 2.
Сортировка вершин по этому argmax. Для каждого разбиения массива на левый подрешетку и правый подмассив вычислите интервал [a, b] of µ, который индуцирует одно и то же разбиение argmax. Пересечь этот интервал до [0, len (u - v)]; если пересечение пустое, то двигаться дальше. В противном случае найдите максимальное расстояние L в левом подмассиве от точки на u - v, индексированной с помощью a, и максимальное расстояние R в правом подмассиве от точки на u - v, индексированной с помощью b. (Стоимость вычисления этих максимумов может быть амортизирована до O (1) для каждого раздела путем сканирования слева направо и справа налево в начале.) Лучший выбор - это µ в [a, b], который минимизирует max (L - (µ - a), R + (b - µ)).