Я столкнулся со следующей проблемой:
Рассмотрим ниже график:
Каким будет дерево кратчайших путей, начинающееся с узла $ A $ возвращается алгоритмом Дейкстры, если мы предположим, что очередь приоритетов реализована в виде двоичной минимальной кучи?
Мое решение:
Я сослался на Дейкстру из CLRS:
С A в качестве начального узла у нас будет минимальная куча bin очереди приоритетов следующим образом:
A{root, 0}
|
Rest all:{∅,∞}
(Обозначение: {parent in SPT, shortest path weight})
Он извлечет A из очереди приоритетов и добавит его в SPT, а A C и AB ослабит:
B{A:5}
/ \
C{A:6} Rest all:{∅,∞}
Извлечет B из очереди приоритетов и добавит его в SPT:
C{A:6}
|
Rest all:{∅,∞}
и расслабится BE:
C{A:6}
/ \
Rest all:{∅,∞} E{B,6}
Далее будет извлечено C и т. Д. Таким образом, SPT будет:
Но не:
Q1. Правильно ли я с выше?
Q2. CLRS al go не указывает, какой узел добавить в SPT, если несколько из них имеют одинаковый вес кратчайшего пути. Следовательно, это зависит от того, как реализована приоритетная очередь. Если не было предоставлено никакой информации о том, как была реализована приоритетная очередь, мы не можем сказать, как будет формироваться SPT. Я прав?