262
правки
Изменения
м
→Двунаправленный поиск
Тонкость этого алгоритма заключается в том, что кратчайший путь <tex>s \rightsquigarrow t</tex> не обязательно пройдёт через вершину <tex>v</tex>. Поэтому после остановки двунаправленного поиска, нам необходимо перебрать все рёбра из вершин, имеющих <tex>d_{forward}</tex> в
вершины с <tex>d_{reverse}(v)</tex> и найти ребро <tex>uv</tex> с минимальным <tex>d_{forward}(u)+\ell(uv)+ d_{reverse}(v) </tex>, и если . Если эта величина меньше, чем длина первоначально найденного пути - то это и есть результат работы алгоритма.
На практике, такой двунаправленный поиск быстрее обычного алгоритма Дейкстры примерно в два раза.
=Двухэтапные алгоритмы=
