Як оцінити складність алгоритму Дейкстри?

Складність алгоритму Дейкстри залежить від способу знаходження вершини v, а також способу зберігання безлічі невідвіданих вершин та способу оновлення міток. Позначимо через n кількість вершин, а через m — кількість ребер у графі G.

Тому що алгоритм Форда-Беллмана все одно не може працювати на графах з негативними циклами. Просто тому що поняття "найкоротший шлях" у таких графах не визначено. Завжди можна пройтися по негативному цикл ще один раз – і отримати ще більш короткий шлях.

Категорія:Алгоритми на графах

Алгоритм Брона – Кербоша
Алгоритм Косарайю
Алгоритм Мальгранжа
Алгоритм Тар'яна
Алгоритм Демукрона
Наближений алгоритм пошуку p-медіан
Завдання про найдовшу дорогу
Топологічне сортування

Пошук у глибину (англ. Depth-first search, DFS) – один із методів обходу графа. Стратегія пошуку в глибину, Як і слідує з назви, полягає в тому, щоб йти «вглиб» графа, наскільки це можливо. Алгоритм пошуку описується рекурсивно: перебираємо всі вихідні з розглянутої вершини ребра.