14. Алгоритм Дийкстры

Дан граф с разными весами ребер – создаем матрицу столбцов - кол-во вершин, строк – 2

Берем вершину 1 и всем смежным с ней вершинам записываем в нижнюю строку 1 – а в

верхнюю вес ребра, которое ведет в эту вершину и так просматриваем все смежные ребра.

Когда смежных ребер больше нет - помечаем вершину как пройденную и больше уже к ней не возвращаемся и переходим к вершине у которой наименьшее число сверху

(пусть это будет вершина 2).

Всем смежным с 2 вершинам внизу пишем 2 а вверху- то что стоит над 2 + вес ребра который ведет в эту вершину.

Если же вдруг число сверху у вершины смежной с 2 уже есть, то если наше значеие меньше то присваиваем его сверху и снизу

если больше нечего помечать – переходим к следующей вершине с наименьшим числом сверху и тд.

Когда все вершины будут помечены – таким путем – числа сверху это и будут кратч пути от вершины 1 до нужной.

Трудоемкость алгоритма Дийкстры

Худший случай – когда вершина, в которую мы ищем кратчайший путь, получит постоянную метку последней .

Тогда у алгоритма будет n-1 итерация. Каждая итерация выполняется за время O(n).

Восстановление пути – O(n).

Общая трудоемкость алгоритма Дийкстры – O(n²)