АиСД-2. 2024-2025. ПЗ-Тест №17. Графы. Часть 3. В1

Какой путь короче от кровати утром понедельника?

• до холодильника

• до ванной

• до Покровки

• обратно в кровать

Какой алгоритм быстрее всего найдет кратчайшие пути на связном
неориентированном графе без весов на ребрах?

• Обход в ширину

• Алгоритм A*

• Обход в глубину

• Алгоритм Дейкстры

Сложность алгоритма Дейкстры не зависит
от используемых структур данных.

• Неправда!

• Да, не зависит!

Какой кратчайший путь из вершины S в вершину T
на этом графе найдет алгоритм Дейкстры?

• S->D->T

• S->B->D->T

• S->A->C->D->T

• S->A->C->E->T

Сложность выполнения операции DECREASE-KEY
в бинарной куче составляет

Фиббоначиева куча улучшает временную сложность операции

• INSERT

• EXTRACT-MIN

• DECREASE-KEY

• DELETE

Худший случай временной сложности алгоритма А* асимптотически лучше
худшего случая временной сложности алгоритма Дейкстры

• Однозначно да!

• Однозначно нет!