Используя кучу Фибоначчи, возможно / легко представить соседей, а также минимальное расстояние

Question

Я пытаюсь разработать реализацию dijkstras с кучами Фибоначчи. То, что я пытаюсь понять, это если возможно представить, кроме минимального расстояния в O (logn) (с удалением), но соседей любого данного узла? Или это нарушает структуру кучи Фибоначчи? В противном случае мне пришлось бы создать список соседей так же, как кучу Фибоначчи.

Answer 1

Вы, кажется, не понимаете, что такое кучи Фибоначчи!

Эта структура независима от Дейкстры или любого другого алгоритма кратчайшего пути и используется только для ускорения алгоритма Дейкстры, ускоряя время для получения вершины с наименьшим расстоянием.

Говоря о том, чтобы поддерживать список соседей как часть структуры кучи Фибоначчи, граничащей с глупостью.

Конечно, вы всегда можете сохранить список соседей, соответствующих каждой вершине в куче (которая технически не является частью структуры кучи), соответствующей этой вершине.