Yuliia CS Osvita

BFS і DFS — два фундаментальні алгоритми обходу графа. Обидва відвідують кожну вершину рівно один раз, але роблять це в різному порядку і через різні структури даних. Саме порядок обходу визначає, яка задача буде вирішена коректно, а яка ні. Як працює BFS BFS алгоритм (Breadth-First Search, обхід у ширину) обходить граф рівень за рівнем. Спочатку всі сусіди стартової вершини, потім їхні сусіди, і так далі. Для цього використовується черга (queue) — структура FIFO: першою обробляється вершина,...

Алгоритм нідерландського вченого Едсгера Дейкстри знаходить найкоротші шляхи від однієї вершини графа до всіх інших у зваженому графі з невід'ємними вагами. Саме на ньому працює більшість навігаційних систем: граф — це дорожня мережа, ваги — відстані або час у дорозі, стартова вершина — ваше поточне місцезнаходження. Задача зводиться до пошуку оптимального маршруту, і Дейкстра вирішує її ефективно. Dijkstra не працює коректно з графами, що містять ребра з від'ємними вагами, тому для таких...

Уявіть граф, де деякі ребра мають від'ємну вагу. Не абстрактно, а цілком реально: наприклад, фінансова мережа, де конвертація валют через певний маршрут дає прибуток, а не витрату. Або логістика, де деякі переміщення субсидовані і знижують загальну вартість маршруту. Саме для таких задач існує Bellman-Ford — алгоритм пошуку найкоротшого шляху, який коректно працює з від'ємними вагами і вміє виявляти негативні цикли. За це він платить вищою складністю, але в задачах, де вага ребра може...