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