Проблемы с пониманием реализации Приоритетной очереди Дейкстры

Question

У меня возникают некоторые проблемы, когда я не могу понять, что именно представляет собой логический поток, в котором мы реализуем Dijkstra. Более точно, с чем у меня проблема, это как мы на самом деле получаем эту очередь приоритетов, мы ее строим (Приоритет Очередь) как мы go про выполнение алгоритма на графе? Или я смотрю на это неправильно? И тогда это все? Стоит ли на этом останавливаться или мы обрабатываем этот вывод еще дальше, помещая полученную информацию в очередь приоритетов в какой-либо другой форме, или это место, где мы останавливаемся?

Я также понимаю процедуру производства соответствующего кратчайшие пути, которые для выбранного узла, рекурсивно следуя ребрам, которые мы взяли, чтобы сформировать кратчайший путь в первую очередь, но как это на самом деле реализовано?

В общем, у меня на самом деле много проблем будучи способным придумывать и / или понимать подходящие реализации алгоритмов во время моего обучения, я прекрасно понимаю алгоритм (и в некоторых случаях я могу придумать близкую замену), но я просто не могу придумать умные способы их реализации, какие-либо предложения?

Answer 1

Мой лучший совет - сначала начать с bfs. Если вы можете реализовать BFS, вы находитесь всего в одном шаге от Дейкстры. BFS использует обычную очередь (сначала в порядке очереди), Dijkstra использует приоритетную очередь (элемент выбирается в соответствии с текущим расстоянием до исходного узла). В этом единственная разница.

Чтобы ответить на ваш конкретный c вопрос:

• Как мы на самом деле получаем эту очередь приоритетов? Вы начинаете с пустой очередь. На каждой итерации (Dijkstra чаще всего реализуется итеративно, а не рекурсивно), вы выбираете узел с наивысшим приоритетом из очереди, и pu sh возвращает в очередь всех соседей этого узла, которые еще не были посещены
• строим ли мы его (очередь приоритетов), как go о выполнении алгоритма на графике? Да, на каждой итерации вы выбираете один узел, а pu sh в несколько узлов в приоритетной очереди
• И что это? Да, это в значительной степени так.
• Незначительные детали: (1) Вы должны отслеживать, какие узлы были выбраны (и никогда не возвращаться обратно) (2) Можно сделать несколько узлов * множественными раз в очередь, и это нормально, (3) Вам нужен массив трассировки, чтобы проследить путь, по которому вы достигнете узла: каждый раз, когда вы помещаете * sh узел в очередь, записывайте трассировку этого узла в быть текущим посещаемым узлом (только что извлеченным из очереди)

Снова начните с BFS, и вы найдете Дейкстру довольно простым