Как быстро найти кратчайший путь при поиске в ширину?
Я использую поиск в ширину, чтобы найти местоположение на графике, и я почти уверен, что мой алгоритм работает правильно, но у меня возникают проблемы с поиском кратчайшего пути к результату, когда я закончу. По сути, я могу добраться от моего начального местоположения до моего конечного местоположения, используя BFS, но я не знаю, как построить кратчайший путь от конца к началу. Любая помощь будет оценена.
Спасибо.
Решение
Одним из вариантов будет следующий. Создайте некоторый способ связывания каждого узла с «родительским» узлом (возможно, хеш-таблицей или, возможно, путем добавления «родительского» поля к любому типу, представляющему узел). Затем, всякий раз, когда вы удаляете узел u из очереди и собираетесь добавить узел v в очередь, установите родительский указатель v на узел u. Это означает, что путь к узлу v был пройден путем следования пути к u, а затем расширения пути на одно ребро, чтобы добраться до v.
После того, как вы это сделали и закончили свою BFS, вы можете прочитать обратный кратчайший путь, начав с конечного узла, затем несколько раз следуя указателю родителя, пока не вернетесь к начальному узлу. Если у вас есть это, вы можете просто изменить этот путь, чтобы получить реальный кратчайший путь.
Надеюсь это поможет!
Другие решения
Других решений пока нет …