262
правки
Изменения
→Двухсторонний запуск
<tex>F</tex> или <tex>B</tex>, в зависимости от того, выполняется ли условие леммы.
===Двухсторонний запускДвунаправленный поиск===Мы можем уменьшить количество посещённых вершин в алгоритме Дейкстры, просто запустив его и из начальной и из конечной вершины. Такая эвристика не испортит скорость работы в худшем случае. Создадим две приоритетных очереди и запустим на одной из них алгоритм Дейкстры, ищущий <tex>d_{forward}(v)</tex> из <tex>s</tex>, а на другой - ищущий <tex>d_{reverse}(v)</tex> из <tex>t</tex>. Алгоритм завершит свою работу, когда какая-нибудь вершина <tex>z</tex> будет удалена из обоих очередей. Тонкость этого алгоритма заключается в том, что кратчайший путь <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>, и если эта величина меньше, чем длина первоначально найденного пути - то это и есть результат работы алгоритма. На практике, такой двунаправленный поиск быстрее обычного алгоритма Дейкстры примерно в два раза.
