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