Алгоритми та структури даних · Middle · Запитання 58 з 75
Що обчислює алгоритм Дейкстри?
- ✓Правильна відповідь: Найкоротші шляхи з однієї вершини, коли ваги невід'ємні
- 2Мінімальне кістякове дерево зваженого графа
- 3Найкоротші шляхи в будь-якому графі, зокрема з від'ємними вагами
Пояснення
Він раз у раз бере невідвідану вершину з найменшою відомою відстанню (із черги з пріоритетом) і релаксує її ребра. З бінарною купою це O((V + E) log V). Від'ємні ваги його ламають.