0

Понятно, как это можно сделать за О(n^4) c помощью стандартного алгоритма Дейкстры. Но хотелось бы узнать, существует ли алгоритм который решает эту задачу быстрее. Думал, что можно как-нибудь модифицировать алгоритм Дейкстры, чтобы он вычислял минимальное расстояние от какой-то вершины до этой же самой вершины, но что-от ничего толкового в голову не пришло. Подскажите, как можно решить эту задачу быстрее, чем за О(n^4).

3
  • Флойда бери. Получится куб.
    – Qwertiy
    24 сен 2018 в 16:04
  • @Qwertiy, алгоритм Флойда в стандартном виде не считает расстояния от вершины i до вершины i. Но спасибо, сейчас попробую его немного изменить.
    – Valery
    24 сен 2018 в 16:15
  • Пока что Флойдом тоже не получилось, завтра еще попытаюсь. Буду рад, если кто-нибудь еще озвучит свои идеи по поводу задачи.
    – Valery
    24 сен 2018 в 17:02

1 ответ 1

1

Есть такой алгоритм (доказательством корректности не интересовался):

Из каждой вершины K запускаем Дейкстру, получаем дерево кратчайших путей, и теперь для каждого ребра AB, не входящего в это дерево (можно получить из массива предков), находим

 T = weight(K-A) + weight(AB) + weight(K-B)

и выбираем минимум из всех T

Получается сложность V * (V^2 + E + E) ~ V^3

1
  • Спасибо. Утром такая мысль тоже появилась)
    – Valery
    25 сен 2018 в 8:05

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.