Алгоритм Дейкстры Этот алгоритм был создан учёным из Нидерландов по имени Эдсгер Дейкстр в 1959 году. Он находит наименьший путь от начальной точки графа до конечной. График работает только если граф без рёбер и имеет отрицательный вес. Алгоритм часто применяеться в программировании и других сферах информационных технологиях (в протоколах маршрутизации (OSPF(динамический маршрутизатор) и IS-IS(маршрутизатор промежуточной системы)).
Пример задачи. Её решение и объяснение Пускай необходимо отыскать самые короткие дистанции с 1-й вершины в плоть до абсолютно всех других. Кружками обозначим вершину, направлениями (линии) – путь среди них (рёбра графа). В кружках отмечены номера вершин, над рёбрами отмечен их вес – протяжённость пути. Рядом с любой вершиной красным отмечена метка – длина которткого пути в данную вершину с вершины 1.
Допустим мы хотим попасть из 1 в 5 самым кратчайшим путём. Инизиализация. Отметка самой вершины 1 предполагается одиноковой 0, отметки других вершин – невозможно огромное число ( в совершенстве – бсконечность). В таком случае данное отображает то, что дистанции с вершины 1 вплоть до других вершин сейчас неизв
Шаг первый. Минимальной отметкой обладает вершина 1. Её рядом находящие вершины это 2, 3 и 6. Пройдём по этим кружкам. Первая рядом находящийся круг вершины 1 – вершина 2, так как расстояние пути до её минимальное. Расстояние пути к ней через вершину 1 будет равна суммесамого короткого пути до её вершины1, длина пути ёё метки и длина ребра идущего из 1-ой в 2-ую вершину, это 0 + 7 = 7. Это меньшее текушей отметки вершины 2, и так новая отметка вершины 2 будет равняться 7 Таким образом все круги рядом проверены. В данный момент самый короткий путь до вершины 1 считается вершина 2 Отметим вершину 1, что будет обозначать что её пути уже проверены.
Шаг второй. Начинаем повторят первый шаг только уже с другими кругом. Это круг 2-ой с отметкой 7.Так же считаем путь от круга 2 до всех рядом находящихся рядом. Рядом находятся круги 1, 3 и 4. Так как мы уже знаем расстояние от вершины 1 до вершины 2 мы начинаем с вершины 3. Снова высчитываем сумму пути. Получаем что путь будет (7 + 10). Также делаем от 2 до вершины 4 и всех последующих.
Так же мы делам и с вершиной 4. Получаем 22(7+15) Шаг третий. Работаем с вершиной 3. После чего мы получаем ещё меньше результаты.
Шар четвёртый.
Шаг пятый.
Шаг шестой.
Таким образом мы нашли самый короткий путь из вершины 1 в вершину 5, что равно 20 единицам.Также мы видем сколько понадобиться что бы дойти от 1 до 5 другими путями.