Линейный алгоритм с одним парой-кратчайшим путем?

Question

Существует ли алгоритм, который решает проблему одной пары-кратчайшего путь в линейное время для смешанных графов (то есть направленные и ненаправленные края или неориентированные ребра, представленные в виде двух ориентированных ребер), с отрицательными, реальными краев-весов и неотрицательные циклы?

Wikipedia упоминает только алгоритмы для одного источника и всех пар вариант задачи. Я знаю, что решение одной из этих проблем также решает проблему одиночной пары , но ни одна из них не работает в линейном времени и со всеми вышеперечисленными критериями.

Итак, существует ли линейная временная алгортма для проблемы с одной парной кратчайшей траекторией со всеми вышеперечисленными критериями?

Answer 1

Нет, нет. Интуитивно ни один алгоритм кратчайшего пути с одной парой, который допускает отрицательные веса ребер, может быть более асимптотически эффективным, чем алгоритм с одним источником, поскольку поиск кратчайшего пути к цели может в худшем случае включать поиск кратчайших путей к каждой из некоторых фиксированных пропорций других узлов (чтобы определить, стоит ли его объединять с краями отрицательного веса).