Алгоритми та структури даних · Senior · Запитання 1 з 75
Чому алгоритм Дейкстри дає хибні результати з від'ємними вагами ребер?
- 1Від'ємні числа взагалі не можна зберігати в бінарній купі
- 2Він зациклюється, щойно будь-яка вага менша за нуль
- ✓Правильна відповідь: Завершена вершина ще може скоротитися через від'ємне ребро
Пояснення
Дейкстра вважає, що коли найближчу вершину взято з черги, жоден пізніший шлях не буде коротшим. Від'ємне ребро руйнує це припущення. Беллман-Форд працює з від'ємними вагами за O(V × E) і ще й знаходить від'ємні цикли.