Рубрики

Алгоритмы | График кратчайших путей | вопрос 2

Для реализации алгоритма кратчайшего пути Дейкстры на невзвешенных графах, который работает за линейное время, необходимо использовать следующую структуру данных:
(A) Очередь
(B) Стек
(С) куча
(D) B-дерево

Ответ: (А)
Объяснение: Самый короткий путь в невзвешенном графе означает наименьшее число ребер, которые необходимо пройти, чтобы достичь пункта назначения в графе. Это та же проблема, что и при решении взвешенной версии, в которой все весовые коэффициенты равны 1. Если мы используем Очередь (FIFO) вместо Приоритетной очереди (Min Heap), мы получаем кратчайший путь за линейное время O (| V | + | E |). В основном мы делаем BFS обход графа, чтобы получить кратчайшие пути.
Тест на этот вопрос

Рекомендуемые посты:

Алгоритмы | График кратчайших путей | вопрос 2

0.00 (0%) 0 votes