Решите, все ли кратчайшие пути от s до t содержат границы

Question

Пусть G = (V;E) - ориентированный граф, все ребра которого имеют неотрицательные веса. Пусть s, t 2 вершины в V, и пусть e ребро в E. Опишите алгоритм, который решает, все ли кратчайшие пути из s в t содержат ребро e.

Итак, вот как вы можете достичь временной сложности Dijsktra: просто запустите Dijkstra из s и вычислите delta(s,t) (вес кратчайшего пути от s до t). Удалите ребро e и снова запустите Djikstra из s в новом графе. Если дельта (s, t) в новом графе увеличилась, это означает, что все кратчайшие пути от s до t содержат ребро e, иначе это не так.

Мне было интересно, есть ли более эффективный алгоритм для решения этой проблемы. Как вы думаете, можно ли победить сложность времени Дейкстры?

заранее спасибо

Answer 1

Ваш подход звучит правильно для меня. Вы просто рассчитываете кратчайший путь с и без возможности взятия края e. Это дает вам 2 поиска Дейкстры.

Есть место для улучшения, если вы перейдете к A*, двунаправленному поиску или восстановите дерево поиска Dijkstra:

• A * ускорит ваш Dijkstra-запрос, но это может оказаться невозможным для вашего графа, так как вы должны иметь возможность определить хорошую границу на вашем оставшемся расстоянии.
• двунаправленный поиск может быть выполнен с обоими поисками, встречающимися по краю. Затем вы можете исследовать все пути с и без края только с одним быстрым двунаправленным запросом + некоторая дополнительная работа для обоих случаев вместо того, чтобы иметь 2 полных Дейкстры, которые очень похожи
• Вы можете искать один раз без края и поддерживать свое дерево поиска. Затем вы добавляете e и обновляете дерево кратчайших путей, начиная с начальной точки e. Если метка конечной точки> метка начальной точки + длина e, конечная точка может быть достигнута быстрее при использовании e. Рекурсивно ищите соседей вашей конечной точки и обновляйте только расстояния, если они могут быть достигнуты быстрее, чем раньше. Должен сэкономить вам немного работы.