Условие:
Алгоритм Дейкстры
Найти кратчайшие пути в графе с весами ≥ 0.
Визуализировать процесс работы алгоритма (вывод шагов в консоль/файл).
Решение:
Ниже приведён пошаговый разбор алгоритма Дейкстры с примером визуализации процесса работы (вывод шагов в консоль). Для примера рассмотрим граф с вершинами A, B, C, D, E и следующим набором рёбер с неотрицательными весами:
Вершины: A, B, C, D, E Рёбра и веса: A → B (6) A → D (1) B → C (5) B → D (2) C → E (5) D → B (2) D → C (1) D → E (1) E → C (5)
Задача: найти кратчайшие пути от исходной вершины A до всех остальных.
Принцип работы алгоритма Дейкстры:
- Инициализация:
- Задаём расстояние до исходной вершины A равным 0, а до остальных – бесконечность (условное обозначение INF). ... graph = { A: [(B, 6), (D, 1)], B: [(C, 5), (D, 2)], C: [(E, 5)], D: [(B, 2), (C, 1), (E, 1)], E: [(C, 5)] }
dijkstra(graph, A)
Ключевые моменты реализации:
- Использование очереди с приоритетом (heapq) позволяет на каждом шаге быстро выбирать вершину с минимальным расстоянием.
- В консоль выводятся выбранная вершина, обновлённые расстояния для соседей и текущее состояние массива расстояний.
- Предшественники (prev) можно использовать для восстановления маршрутов.
Таким образом, алгоритм Дейкстры находит кратчайшие пути от начальной вершины A до всех остальных вершин в графе с неотрицательными весами, а визуализация процесса помогает отследить, какие обновления происходят на каждом шаге.