Поиск пути между всеми точками с использованием алгоритма аппроксимации

Вот приближенный алгоритм, который в среднем должен давать лучшие результаты, чем наивный жадный алгоритм:

1. Считайте граф полным — между каждой парой вершин есть ребро, всего n(n-1)/2 ребер.
2. Отсортируйте ребра в порядке убывания их веса/расстояния.
3. Итерировать от ребра с наибольшим расстоянием до ребра с наименьшим расстоянием и удалить его, если после удаления этого ребра обе его конечные точки по-прежнему имеют степень не ниже ceil(n/2) (теорема Дирака для обеспечения существования гамильтонова цикла). Вы можете использовать более сильный результат, например теорему Оре, чтобы обрезать еще больше ребер, но сложность вычислений возрастет.
4. На оставшемся графике используйте жадный алгоритм, чтобы найти гамильтонов цикл. Жадный алгоритм в основном начинает с 1 и продолжает выбирать ребро с наименьшим расстоянием до узла, который еще не является частью цикла. Так что в вашем примере он сначала выберет 1 -> 2, затем 2-> 4, затем 4-> 5 и так далее. Последняя выбранная вершина будет иметь обратный путь к 1.

Вы можете напрямую использовать жадный алгоритм, указанный в шаге 4, на входном графике, но шаги предварительной обработки 1-3 в целом должны значительно улучшить ваши результаты на большинстве графиков.

Похоже на TSP, за исключением того, что вам нужно минимизировать максимальную длину между двумя городами, а не общую ( что, вероятно, делает его принципиально другим).

Моя мысль примерно такая:

create edges between each pair of cities
while (true)
  next = nextLongestEdge
  if (graph.canRemove(next)) // this function may be somewhat complicated,
                             // note that it must at the very least check that every node has at least 2 edges
    graph.remove(next)
  else
    return any path starting and ending at 1 from the remaining edges