Как работает алгоритм дейкстры?

мне на экзамене как раз попалась дейкстра, руками на графе из 6 вершин полдоски исписал но защитил

если веса отрицательные лучше сразу форд беллман брать, дейкстра там ошибается молча что хуже всего

Суть Берёшь ближайшую необработанную вершину, обновляешь расстояния до её соседей, повторяешь, пока не обойдёшь весь граф.

• Алгоритм Дейкстры ищет кратчайший путь от одной стартовой вершины до всех остальных в графе с неотрицательными весами рёбер.
• Каждой вершине сначала присваивается расстояние "бесконечность", кроме стартовой, у неё расстояние 0.
• На каждом шаге алгоритм берёт ещё не обработанную вершину с наименьшим текущим расстоянием, вот ответ на вопрос "откуда он знает, какую взять следующей": просто смотрит на уже посчитанные расстояния и выбирает минимальное.
• От выбранной вершины проверяются все соседи: если путь через неё короче, чем известный сейчас, расстояние соседа обновляется.
• Вершина помечается обработанной и больше не пересматривается, алгоритм переходит к следующей необработанной вершине с минимальным расстоянием.
• Процесс повторяется, пока все вершины не станут обработанными, тогда у каждой будет записано кратчайшее расстояние от старта.

1. Ставим расстояние 0 стартовой вершине, всем остальным, бесконечность.
2. Берём необработанную вершину с минимальным расстоянием.
3. Обновляем расстояния до её соседей, если через неё путь короче.
4. Помечаем вершину обработанной.
5. Повторяем, пока не останется необработанных вершин. Предупреждение: с отрицательными весами рёбер алгоритм даёт неверный результат, для таких графов нужен другой метод, например Беллмана-Форда.