Алгоритм Бхандари - sergeresko/Lem_in-explanation GitHub Wiki
Помню, из статьи не всё было ясно и кое о чём приходилось догадываться. Вот шаги алгоритма Бхандари для лучшего понимания:
Граф имеет исходный вид (все рёбра двунаправленные с весом 1). Если это первый запуск алгоритма, то все pred/succ равны NULL; если не первый — некоторые из них не NULL и описывают уже найденные пути. У комнат start и end они всегда NULL.
1) modify graph
для каждого пути, обозначенного с помощью pred/succ, произвести раздвоение вершин (включая действия, касающиеся рёбер)
2) find path
выполнить алгоритм Дейкстры (перед его запуском надо, чтоб у всех комнат, в т.ч. созданных в результате раздвоения, значения полей были сброшены к distance = ∞ и parent = NULL)
Если алгоритму Дейкстры удалось найти путь, то он состоит из комнат, в которые можно попасть, переходя по полю parent, начиная с комнаты end. Если ему не удалось найти путь, то parent комнаты end равен NULL.
3) adjust parents
подготовить граф к слиянию вершин (нужно некоторым комнатам поменять значения parent, чтобы при последующем удалении комнат, которые образовались при раздвоении, цепочка parent не нарушилась)
Например, допустим, что некоторая вершина X исходного графа была раздвоена: из неё получились X' и X". Может оказаться, что путь, описываемый полями parent, проходит через X' либо через X" либо через обе X' и X". Нужно добиться того, чтобы в любом из этих случаев после объединения этих вершин обратно в X путь проходил через X.
4) restore graph
для каждого пути, обозначенного в графе с помощью pred/succ, произвести слияние вершин (включая действия, касающиеся рёбер)
В результате граф станет идентичным исходному, за исключением значений distance и parent.
5) combine paths
обновить значения pred/succ в соответствии с правилом наложения путей
Т.е. мы проходим по пути, ведущему от end к start через поля parent, и, если какое-то его ребро ещё не обозначено в pred/succ, обозначаем его; иначе (если оно уже обозначено), «удаляем» его, устанавливая соответствующие pred/succ в NULL. В итоге pred/succ будут описывать новый набор путей.
Дальше: Иллюстрация