Складність алгоритму Дейкстри залежить від способу знаходження вершини v, а також способу зберігання безлічі невідвіданих вершин та способу оновлення міток. Позначимо через n кількість вершин, а через m — кількість ребер у графі G.
Тому що алгоритм Форда-Беллмана все одно не може працювати на графах з негативними циклами. Просто тому що поняття "найкоротший шлях" у таких графах не визначено. Завжди можна пройтися по негативному цикл ще один раз – і отримати ще більш короткий шлях.
Категорія:Алгоритми на графах
- Алгоритм Брона – Кербоша
- Алгоритм Косарайю
- Алгоритм Мальгранжа
- Алгоритм Тар'яна
- Алгоритм Демукрона
- Наближений алгоритм пошуку p-медіан
- Завдання про найдовшу дорогу
- Топологічне сортування
Пошук у глибину (англ. Depth-first search, DFS) – один із методів обходу графа. Стратегія пошуку в глибину, Як і слідує з назви, полягає в тому, щоб йти «вглиб» графа, наскільки це можливо. Алгоритм пошуку описується рекурсивно: перебираємо всі вихідні з розглянутої вершини ребра.