Куча в алгоритме Дейкстры
может кто-нибудь объяснить, в чем важность HeapDesc в алгоритме ШейнСондерса Дейкстры и как это здесь используется?
В общем, я знаю, как работает алгоритм Дейкстры. Но я не получаю кучу части в реализации.
Это большой код. поэтому я публикую ссылку, если вы хотите посмотреть на нее.
Вот иди http://www.cosc.canterbury.ac.nz/research/RG/alg/dijkstra.cpp
Решение
В Dijkstra вам нужна эффективная структура данных, которая дает вам преимущество минимальной стоимости, которая позволяет вам достичь другой вершины.
отвал это именно та структура данных, которая позволяет хранить набор ребер и эффективно извлекать набор с минимальными затратами.
Другие решения
HeapDesc, вероятно, реализует шаблон проектирования фабрики для создания различных типов кучи. Если вы проверите файл http://www.cosc.canterbury.ac.nz/research/RG/alg/dijkstra.h, вы заметите, что переменная heap в конструкторе является объектом типа Heap.
Посмотрите на эту статью для фабрики шаблон дизайна.
http://en.wikipedia.org/wiki/Factory_method_pattern
Алгоритм Дейкстры включает в себя множество «поиска пути с наименьшей стоимостью».
Мин или макс поиск это то, что отвал оптимизирован для (O (1)), и именно поэтому он используется.
Относительно HeapDesc само по себе, это просто кажется заводской метод, используется для выделения объекта Heap.
Heap *newInstance(int n) const { return new T(n); }; // from heap.h