Представь карту городов: вершины это точки, а рёбра это дороги с длиной или стоимостью. Мы начинаем со стартовой точки и сначала считаем расстояние до неё равным нулю. До всех остальных путь пока неизвестен. Дальше алгоритм каждый раз выбирает ближайшую непроверенную вершину и обновляет расстояния до её соседей. Если найден путь короче, старое значение заменяется новым. Так шаг за шагом мы получаем кратчайшие расстояния до всех точек. Главное правило: Дейкстра работает только там, где веса рёбер не отрицательные.
Алгоритм Дейкстры нужен, чтобы найти самый короткий путь в графе.
Представь карту городов: вершины это точки, а рёбра это дороги с длиной или стоимостью.
Мы начинаем со стартовой точки и сначала считаем расстояние до неё равным нулю.
До всех остальных путь пока неизвестен.
Дальше алгоритм каждый раз выбирает ближайшую непроверенную вершину и обновляет расстояния до её соседей.
Если найден путь короче, старое значение заменяется новым.
Так шаг за шагом мы получаем кратчайшие расстояния до всех точек.
Главное правило: Дейкстра работает только там, где веса рёбер не отрицательные.
